吉林省高校专升本 计算机科学与技术专业综合试题及答案 数据结构.pdf

吉林省普通高校专升本教育试点考试

计算机科学与技术专业综合试卷

（数据结构部分共90分）

一、填空题（每小题2分，共26分）

1.栈的主要特点是_先进后出_；队列的主要特点是__先进先出__。

2.在一长度为n的向量中的第i个元素（1≤i≤n）之前插入一个元素时，需向后

移动__n-i+1__个元素。

3.对于一个具有n个结点的单链表，在已知P所指结点都插入一个新结点的时

间复杂度为__O(1)__；在给定值为x的结点后插入一个新结点的时间复杂度

为__O(n)___。

4.设n行n列的下三角矩阵A已压缩到一维数组s[0…n*(n+1)/2]中，若按行序

为主存储，则A[i][j]对应的s中的存储位置为__i(i-1)/2+j-1__。

5.将f=1+1/2+1/3+…+1/n转化成递归函数，其递归出口是__f(1)=1__，递归体

是__f(n)=f(n-1)+1/n___。

6.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含

的结点数至少为__2h-1__。

7.具有n个叶子结点的哈夫曼树中，其结点总数为__2n-1__。

h

8.对一个满二叉树，m个树叶，n个结点，深度为h，则n=__2-1__。

9.判定一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用

__深度优先遍历___算法。

10.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是__哈希表

查找__。

1

2

11.快速排序在最坏情况下的时间复杂度为__O(n)__。

12.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序方法建立

的初始堆为_（84，79，56，38，40，46）_。

13.直接存取文件是用__哈希__方法组织的。

二、单项选择题（每小题2分，共20分）

1.线性表的顺序存储结构是一种（）的存储结构；线性表的链式存储结构是

一种（）的存储结构。

A.随机存取，顺序存取B.顺序存取，随机存取

C.索引存取，散列存取D.散列存取，随机存取

2.表达式a*(b+c)-d的后缀表达式为（）。

A.abcd+-*B.abc+*d-C.abc*+d-D.-+*abcd

3.在一个单链中，若P所指结点不是最后的结点，在P之后插入S所指结点，

则执行（）。

A.S-next=P;P-next=S;B.S-next=P-next;P-next=S;

C.S-next=P-next;P=S;D.P-next=S;S-next=P;

4.一个栈的入栈序列为1，2，…，n，其输出序列为P1，P，…，Pn，若P=n，

21

则P为（）。

i

A.iB.n-iIC.n-i+1D.不确定

5.数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1

到10，从首地址为SA开始连续存放在存储器内，该数组按行序存放时，元

素A[8][5]的起始地址为（）。

A.SA+141