内容发布更新时间 : 2024/5/3 8:50:01星期一 下面是文章的全部内容请认真阅读。
数据结构模拟试卷(一)及参考答案
一．单项选择题（本大题共15小题，每小题2分，共30分）
1．如果只想得到1024个元素组成的序列中的前5个最小元素，那么用( A )方法最快。 A、起泡排序 B、快速排序
C、堆排序 D、直接选择排序 2．算法分析的目的是（ B ） A．辨别数据结构的合理性 B．评价算法的效率
C．研究算法中输入与输出的关系 D．鉴别算法的可读性
3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ C ） A．插入 B．删除 C．定位 D．排序
4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ D ）
A．3，2，6，1，4，5 B．5，6，4，2，3，1 C．1，2，5，3，4，6 D．3，4，2，1，6，5
5．设串sl=″DataStructureswithJava″,s2=″it″，则子串定位函数index(s1,s2)的值为（ A ）
A．15 B．16 C．17 D．18 6．一个顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（ B ）。
A. 108 B. 112 C. 116 D. 120
7．从一个具有n个结点的单链表中查找其值等于x的结点，在查找成功的情况下，平均需要比较（ C ）个结点。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ D ） A．不一定相同 B．互为逆序 C．都不相同 D．都相同 9．高度为5的二叉树至多有结点数为（ A ）
A. 63 B. 32 C. 24 D.64
10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ B ） A．图中每个顶点的出度 B．图中每个顶点的入度 C．图中弧的条数 D．图中连通分量的数目 11．图的邻接矩阵表示法适用于表示（ C ） A．无向图 B．有向图 C．稠密图 D．稀疏图 12．在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指的结点，则
执行（ D ）。
A. s->next=p; p->next=s B. p-next=s; s->next=p
C. p=s; s->next=p->next D. s->next=p->next; p->next=s
13．下列排序算法中，其时间复杂度和记录的初始排列无关的是（ A ） A．直接选择排序 B．插入排序 C．快速排序 D．冒泡排序 14．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进
行比较的关键字依次为（ B ） A．f,d,b B．f,c,b C．g,c,b D．g,d,b
15．如下图所示的4棵二叉树中，（ C ）不是完全二叉树。
A B C D
二．填空题（本大题共15小题，每小题2分，共30分）
1. 在数据结构中，数据的逻辑结构分线性结构和 非线性结构 。
2. 称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和___ f(n)____的数
量级相同。
3. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_____
O(n)____。
4. 假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13
和17，则当前尾指针的值为__10____。
5. 对于栈只能在___栈顶_____插入和删除元素。 6. 通常从正确性、____可使用性___、可读性、效率和健壮性等5个方面评价算法（包
括程序）的质量。
7. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。
8. 若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量
为3的希尔排序，则得到的结果为 (15,02,21,24,26,57,43,66,80,48,73) 。
9. 在索引存储中，若一个索引项对应数据对象表中的一个表项（记录），则称此索引
为 稠密 索引，若对应数据对象表中的若干个表项，则称此索引为 稀疏 索引。
10. 二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为 89 。 11. 广义表A((a，b，c)，(d，e，f))的表尾为 （(d，e，f)） 。
12. 设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出
栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 3 。 13. 根据一组记录(56，42，50，64，48)依次插入结点生成一棵AVL树(高度平衡的二
叉搜索树)时，当插人到值为 50 的结点时需要进行旋转调整。 14. n（n＞0）个顶点的无向图最多有 n(n-1)／2 条边。
15. 设无向图的邻接表如下图所示，则该图的边的数目是 5 。
三．判断题(本大题共10小题，每小题1分，共10分) （×）链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
（√）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 （×）通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 （√）一个广义表的表尾总是一个广义表。
（×）对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
（√）当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
（×）存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
（√）进行折半搜索的表必须是顺序存储的有序表。 （×）直接选择排序是一种稳定的排序方法。
（×）在用单链表表示的链式队列中，队头在链表的链尾位置。
四．问答题 (本大题共5小题，每小题6分，共30分) 1．由如图所示的二叉树，回答以下问题。
a.其中序遍历序列为 d g b a e c h i f 。 b.其先序遍历序列为 a b d g c e f h i 。
c.其后序遍历序列为 g d b e i h f c a 。
a
b c e d f
h g i
2．已知图G=(V,E)，其中V＝{a,b,c,d,e,f,g}，E＝
｛
b
c a g
f d e
邻接矩阵： a b c d e f g
0 1 0 0 0 0 1 a
0 0 0 0 0 0 1 b
0 1 0 0 0 0 0 c 0 0 1 0 0 1 0 d 0 0 0 1 0 0 0 e
1 0 0 0 1 0 0 f
0 0 1 1 0 1 0 g