西南大学网院[0012]《数据结构》在线作业资料

欧阳老师

西南大学网络与继续教育学院
欢迎您！%E6%9D%8E%E8%87%A3%E8%81%AA同学学号：W16105571146004答案

单项选择题
1、
用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15，21，25，47，27，68，35，84
15，20，21，25，35，27，47，68，84
15，20，21，25，27，35，47，68，84
则所采用的排序方法是（）
1.A.选择排序
2.希尔排序
3.快速排序
4.归并排序
2、
不定长文件是指（）
1.记录的长度不固定
2.关键字项的长度不固定
3.字段的长度不固定
4.文件的长度不固定
3、
如下陈述中正确的是（）
1.串中元素只能是字母
2.串是一种特殊的线性表
3.串的长度必须大于零
4.空串就是空白串
4、
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）
1.O（m+n）
2.O（n）
3.O（m）
4.O（1）
5、
设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）
1.F.front=(front+1)%m
2.front=(front1)%m
3.front=front+1
4.front=(front+1)%(m1)
6、计算机算法必须具备输入、输出和等5个特性
1.易读性、稳定性和安全性
2.确定性、有穷性和稳定性
3.可行性、可移植性和可扩充性
4.可行性、确定性和有穷性
7、有8个结点的无向图最多有条边
1.112
2.56
3.28
4.14
8、不含任何结点的空树
1.是一棵树
2.是一棵二叉树
3.是一棵树也是一棵二叉树
4.既不是树也不是二叉树
9、一棵深度为6的满二叉树有个分支结点
1.30
2.31
3.32
4.33
10、把一棵树转换为二叉树后，这棵二叉树的形态是
1.唯一的
2.有多种
3.有多种，但根结点都没有左孩子
4.有多种，但根结点都没有右孩子
11、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是
1.O(log2n)
2.O(1)
3.O(n)
4.O(nlog2n)
12、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）
1.快速排序
2.堆排序
3.归并排序
4.直接插入
13、设哈希表长m=14哈希函数H(key)=keyMOD11。表中已有4个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空，如用二次探测再散列处理冲突，则关键字为49的地址为
1.3
2.5
3.8
4.9
14、设一棵完全二叉树有300个结点，则共有个叶子结点
1.150
2.152
3.154
4.156
15、由３个结点所构成的二叉树有种形态.
1.2
2.3
3.4
4.5
16、设有两个串p和q，求q在p中首次出现的位置的运算称作：
1.连接
2.模式匹配
3.求子串
4.求串长
17、
栈中元素的进出原则是
1.先进先出
2.后进先出
3.栈空则进
4.栈满则出
18、链表是一种采用存储结构存储的线性表.
1.顺序
2.星式
3.链式
4.网状
19、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
1.存储结构
2.顺序存储结构
3.逻辑结构
4.链式存储
20、一个具有n个顶点的有向图最多有（）条边
1.n(n1)/2
2.n(n+1)/2
3.n(n1)
4.n2
21、判断一个循环队列Q（最多n个元素）为满的条件是
1.Q&gtfront==(Q&gtrear+1)%n
2.Q&gtrear==Q&gtfront+1
3.Q&gtfront==(Q&gtrear1)%n
4.Q&gtrear==Q&gtfront
22、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是
1.p=p&gtnext
2.p=p&gtnext&gtnext
3.p&gtnext=p
4.p&gtnext=p&gtnext&gtnext
23、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是
1.p&gtnext=qq&gtprior=pp&gtnext&gtprior=qq&gtnext=q
2.q&gtprior=pq&gtnext=p&gtnextp&gtnext&gtprior=qp&gtnext=q
3.q&gtnext=p&gtnextq&gtprior=pp&gtnext=qp&gtnext=q
4.p&gtnext=qp&gtnext&gtprior=qq&gtprior=pq&gtnext=p&gtnext
24、
在一棵度为3的树中度为3的结点个数为2度为2的结点个数为1则度为0的结点个数为()
1.C.7
2.6
3.4
4.5
25、
算法指的是（）
1.B.排序算法
2.E.解决问题的计算方法
3.计算机程序
4.解决问题的有限运算序列
26、
在含n个顶点和e条边的无向图的邻接矩阵中零元素的个数为()
1.n*n－2e
2.e
3.n*n－e
4.2e
27、
线性表采用链式存储时，结点的存储地址（）
1.D.连续与否均可
2.必须是连续的
3.和头结点的存储地址相连续
4.必须是不连续的
多项选择题
28、抽象数据类型的组成部分分别为
1.数据对象
2.存储结构
3.数据关系
4.基本操作
29、不具有线性结构的数据结构是：
1.图
2.栈
3.广义表
4.树
30、算法分析的两个主要方面是()
1.正确性
2.简单性
3.空间复杂度
4.时间复杂度
判断题
31、链表的每个结点中都恰好包含一个指针
1.A.√
2.B.
32、如果将所有中国人按照生日来排序，则使用哈希排序算法最快
1.A.√
2.B.
33、折半查找只适用于有序表，包括有序的顺序表和链表
1.A.√
2.B.
34、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。
1.A.√
2.B.
35、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。
1.A.√
2.B.
主观题
36、中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。
参考答案：
有序
37、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间.
参考答案：
顺序表
38、设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。
参考答案：
d/2
39、
快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。
参考答案：
O(n*n)，O(nlog2n)
40、
设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。
参考答案：
9，501
41、
为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。
参考答案：
构造一个好的HASH函数，确定解决冲突的方法
42、
设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。
参考答案：
出度，入度
43、
在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素.
参考答案：
n1
44、
参考答案：
（1）Push(SN%8)（2）!StackEmpty(S)
45、带头结点的单链表head为空的判定条件是（）。
参考答案：
head&gtnext==NULL
46、1.数据的存储结构可用四种基本的存储方法表示，它们分别是().
2.在具有n个元素的循环队列中，队满时具有个元素.
3.广义表A=((a)a)的表头是（）。
4.稀疏矩阵一般的压缩存储方法有()和（）两种。
5.用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中，若结点R[i]有右孩子，则其右孩子是（）
6.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是()
7.n个顶点的连通图至少有边。
8.已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（）次。
9.对一棵二叉排序树按（）遍历，可得到结点值从小到大的排列序列。
10.一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（）方法
参考答案：
1&lt\/font&gt.顺序、链式、索引、散列&lt\/font&gt&lt\/p&gt
2.n1&lt\/font&gt&lt\/p&gt
3.(a)&lt\/font&gt&lt\/p&gt
4.三元组十字链表&lt\/font&gt&lt\/p&gt
5.R[2i+1]&lt\/font&gt&lt\/p&gt
6.连通图&lt\/font&gt&lt\/p&gt
7.n1&lt\/font&gt&lt\/p&gt
8.1&lt\/font&gt&lt\/p&gt
9.中序&lt\/font&gt&lt\/p&gt
10.堆排序&lt\/font&gt&lt\/p&gt
&lt\/font&gt&lt\/p&gt
47、
下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedefstruct{ints[100]inttop}sqstack
voidpush(sqstack&ampstackintx)
{
if(stack.top==m1)printf(“overflow”)
else{_____________________________________}
}
参考答案：
stack.top++，stack.s[stack.top]=x
48、
一个循环队列Q的存储空间大小为M其队头和队尾指针分别为front和rear，则循环队列中元素的个数为：。
参考答案：
(rearfront+M)%M
49、
设串长为n，模式串长为m，则KMP算法所需的附加空间为()
参考答案：
O(m)
50、
一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。
参考答案：
0123456789101112
78
15
03
57
45
20
31
23
36
12
查找成功的平均查找长度：ASLSUCC=14/10=1.4
51、写出用直接插入排序将关键字序列{542389486450259034}排序过程的每一趟结果。
参考答案：
52、
阅读以下二叉树操作算法，指出该算法的功能。
Template&ltcalsstype&gtvoidBinTree&ltType&gt：：
unknown(BinTreeNode&ltType&gt*t){
BinTreeNode&ltType&gt*p=t*temp
if(p!=NULL){
temp=p→leftchild
p→leftchild=p→rightchild
p→rightchild=temp
unknown(p→leftchild)
undnown(p→rightchild)
}
}
该算法的功能是：________________________________
参考答案：
该算法的功能是：交换二叉树的左右子树的递归算法。
53、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。
参考答案：
EDCBIHJGFA
54、
已知一组记录的排序码为（46，79，56，38，40，8095，24），写出对其进行快速排序的每一次划分结果。
参考答案：
划分次序
划分结果
第一次
[382440]46[56809579]
第二次
24[3840]46[56809579]
第三次
24384046[56809579]
第四次
2438404656[809579]
第五次
243840465679[8095]
第六次
2438404656798095
55、设待排序序列为{10184361219158}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。
参考答案：
56、写出下列程序的时间复杂度
s=0
fori=0i&ltni++)
for(j=0j&ltnj++)
s+=B[i][j]
sum=s
参考答案：
O（n^2）
57、设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有
①front=11，rear=19②front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？
参考答案：
（1）L=（40＋19－11）%40=8（2）L=（40＋11－19）%40=32
58、
写出下列程序的时间复杂度
for(i=0i&ltni++)
for(j=0j&ltmj++)
A[i][j]=0
参考答案：
O（m*n）
59、
设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。
参考答案：
哈夫曼树略，WPL=78
60、
设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=kmod7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
参考答案：
略
61、
设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
参考答案：
链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。

更多免费学习资料请登录www.openhelp100.com