数据结构试题2

数据结构试题2
一、单项选择题（每小题3分，共30分）
1、下列排序算法中，（ ）排序在每趟结束后，不一定能选出一个元素放到其排好序的最终
位置上。
A、选择 B、冒泡 C、归并 D、堆
2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则
采用（ ）存储方式最节省运算时间。
A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表
3、串的长度是（ ）。
A、串中不同字符的个数 B、串中不同字母的个数
C、串中所含字符的个数且字符个数大于 0 D、串中所含字符的个数
4、有一个散列表，表长度 m为 100，采用除余法构造散列函数，即 H(k)=k%P,(P 小于等
于 m)，为使散列函数有较好的性能，P 的选择应是（ ）。
A、99 B、97 C、91 D、93
5、在包括 n个键值的二叉排序树中查找一个键值，其平均比较的量级为（ ）。
A、O(n) B、O(logn) C、O(nlogn) D、O(n)
6、对有14个元素的有序表 A[1„14]作二分查找，查找A[4]时的被比较元素依次为（ ）。
A、A[1]，A[2]，A[3]，A[4] B、A[1]，A[14]，A[7]，A[4]
C、A[7]，A[3]，A[5]，A[4] D、A[7]，A[5]，A[3]，A[4]
7、具有65个结点的完全二叉树其深度为（ ）。
A、8 B、7 C、6 D、5
8、带权有向图G用邻接矩阵 A存储，则顶点 i的入度等于 A中（ ）。
A、第 i行非无穷元素之和 B、第 i列非无穷元素之和
C、第 i行非零且非无穷元素个数 D、第 i列非零且非无穷元素个数
9、队列操作的原则是（ ）。
A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除
10、若表R在排列前已按元素键值递增顺序排序，采用（ ）的比较次数少。
A、直接插入排序 B、快速排序 C、归并排序 D、选择排序
二、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１ 分，共１０分）
1、在栈空的情况下，不能做退栈运算，否则产生下溢。 （ ）
2、在快速排序算法中，取待排序的 n个记录中的第一个的键值为基准，将所有记 录分为
两组，读记录就排在这两组的中间，这也是该记录的最终位置。 （ ）
3、在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使 用二分查
找方法。 （ ）
4、设有键值序列（k1，k2，„，kn），当 i>n/2时，任何一个序列（k1，k2，„，kn）一定
是堆。 （ ）
5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度h。
（ ）
6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为
零。 （ ）
7、双循环链表中，任一结点的前驱指针均为不空。 （ ）
8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复 杂度都是
O(n),因而两种存储方式的插入、删除运算所花费的时间相同。 （ ）
9、如果有向图 G=(V，E)的拓扑序列不唯一，则图中必有两条弧和 存在。（ ）
10、矩阵压缩存储的方法是用三元组表存储矩阵元素。 （ ）
三、填空题（每小题2分，共20分）
1、设 sq[1„maxsize]为一个顺序存储的栈，变量 top 指示栈顶元素的位置。作进栈操作时，
必须判别____。如要把栈顶元素取到 x中，需执行语句__ ___。
2、设一个二叉树共有50个叶结点（终端结点），则共有_______个度为2的结点。
3、在单链表中，若要在指针p所指结点(data，next)后插入指针s所指结点，则需要执行下
列两条语句：s→next=p→next;_________。
4、3个结点可构成_________棵不同形状的树。
5、利用直接选择排序算法对 n个记录进行排序，最坏情况下，记录交换的次数为 _______
6、如果含 n个顶点的图是一个环，则它有_________棵生成树。
7、如果要将序列{50，16，23，68，94，70，73}建成堆，则只需把 16 与______ 相互交换
即可。
8、在一棵高度为 h 的平衡二叉树中，最少含有_________个结点，最多含有 2 h -1 个结点。
9、假设一个 9 阶的上三角矩阵 A 按列优先顺序压缩存储在一维数组 B 中，其中 B[0]存
储矩阵中第1个元素a11，则B[31]中存放的元素是___________。
10、在单链表上难以实现的排序方法有___________和堆排序。
四、简答题（每题10分，共60分）
1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指 针，能否
将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？
2、 一项工程由P1、 P2、 „、 P6六项子工程组成， 这些工程之间有下列关系： P1P3表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。
3、设散列表长度为 14，散列函数 H(x)=∟ 2 / i」，其中 i为键值中第一个字母在字母表中
的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug， Sep，Oct，
Nov，Dec，用拉链法处理冲突，要求：
（1）构造散列表。
（2）求出在等概率情况下，查找成功的平均查找长度。
4、设下图所示的二叉树是由森林转化而成的，试将它还原为森林。

5、何为队列的“假溢出”现象？如何解决？
6、分析以下程序段中语句x=x+y的执行次数。
x=0; y=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=1;k<=j;k++)
x=x+y;
五、算法设计题（每题15分，共30分）
说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。
1、设计一个算法，求出指定结点在给定的二叉排序树中所在的层次。
2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删
除表中所有值大于 min且小于 max的元素（若表中存在这样的元素）的算法。
数据结构试题2答案
一、1——5：CDDBB 6——10：CBDAA
二、1——5：√√√ⅹⅹ 6——10：ⅹ√ⅹⅹⅹ
三、1、① 栈是否满（或top=maxsize） ②x=sq[top] 2、49 3、p→next=s;
4、2 5、n-1 6、n 7、50 8、h 9、A82 10、快速排序
四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除 p 结点。双链表
的删除时间复杂度为O(1)，单循环链表删除p结点的时间复杂度为O(n)。
2、答案：可给出有向图表示各子工程间的关系按照入度为零的结点先访问的原则，访问各
个结点即可。
找出3个可能的施工顺序如下：
P1，P2，P3，P4，P5，P6
P1，P4，P2，P3，P5，P6
P4，P5，P1，P2，P3，P6
3、答案：（1）：

（2）ASL=（1*7+2*4+3*1）/12=5。
4、答案：

5、答案：队列的“假溢出”现象是指用数组实现的顺序队列中，对尾指针已达到数组的下
标上界产生上溢而对头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环队
列技术使数组空间首尾相连。
6、答案：
五、1、答案：
int level(t,p)；
bitree *t,*p;
{ int count;
count=0;
if(t==NULL)
return(0);
else { count=count+1; while(t→data!=p→data) {
if(t→datat= t→rchild;
else
t= t→lchild;
count=count+1; } }
return(count);
}
2、答案：
delete(head,max,min) //删除有序单链表中所有值大于min且小于
max 的元素 linklist *head;
int max,min;
{ linklist *p,*q;
if(head!=NULL)
{ q=head;
p=head→next; }
while((p!=NULL)&&(p→datap=p→next;
q→next=p; }