2024年4月30日发(作者：)

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。

A、不确定 B、2n C、2n+1 D、2n-1

2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是

字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，

gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，

cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储

方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表

4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。

A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉

树。

A、空或只有一个结点 B、高度等于其结点数

C、任意结点无左孩子 D、任意结点无右孩子

6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的 是

（ ）。

A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排

序

7、快速排序算法在最好情况下的时间复杂度为（ ）。

A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)

8、已知数据表 A中每个元素距其最终位置不远，则采用（ ）排序算法最 省时

间。

A、堆排序 B、插入排序 C、直接选择排序 D、快序排

序

9、带权有向图G用邻接矩阵 A存储，则顶点 i的入度为 A中（ ）。

A、第 i行非∞的元素之和 B、第 i列非∞的元素之和

C、第 i行非∞且非 0的元素之和 D、第 i列非∞且非 0的元素之和

10、在有 n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比 较

次数的数量级为（ ）。

A、O(n) B、O(n 2 ) C、O(nlogn) D、O(logn)

二、判断题 （认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，

共10分）

1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可

访问该图的每个顶点。 ( )

2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅

与表的个数有关，而且与每一块中的元素个数有关。 ( )

3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 ( )

4、图G的最小生成树的代价一定小于其他生成树的代价。 ( )

5、已知一棵树的先序序列和后序序列，一定能构造出该树。 ( )

6、对一个堆按层次遍历，不一定能得到一个有序序列。 ( )

7、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT

中的结点也一定是叶子结点。 ( )

8、不管 ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Push(x,S) 的

耗时均为 O(n)。 ( )

9、如果删除二叉排序树中一个结点，再按照二叉排序树的构造原则重新插入 上

去，一定能得到原来的二叉排序树。 ( )

10、快速排序是排序算法中最快的一种。 ( )

三、填空题（每小题2分，共20分）

1、在双向循环表中，在 p所指的结点之后插入指针 f所指的结点，其操作为 ：

___ ______=p;f→next=p→next;_____=f; p→next=f。

2、在有序表 A[1…20]中，采用二分查找算法查找元素值等于 A[12]的元素，所

比较过的元素的下标依次为__________。

3、若某串的长度小于一个常数，则采用_________存储方式最节省空间。

4、在有 n个顶点的有向图中，每个顶点的度最大可达_________。

5、已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为

__________。

6、设键值序列为{K1，K2，…，Kn},用筛选法建堆则必须从第_______个元 素

开始筛选。

7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_________。

8、直接选择排序算法在最好情况下所作的交换元素的次数为___ _____。

9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行_______比赛。

10、下列排序算法中， 占用辅助空间最多的是_________( 堆排序， 希尔排序，

快速排序，归并排序)。

四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头

指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？

2、设有一组关键字（17，13，14，153，29，35）需插入到表长为12的散列表

中，请回答以下问题：

（1）设计一个适合该散列表的散列函数。

（2）用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决

冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为多

少？

3、对 n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下

列有关问

（1）图中有多少条边？

（2）任意两个顶点 i和 j是否有边相连？

（3）任意一个顶点的度是多少？

4、已知下面二叉排序树的各结点的值依次为1…9，请标出各结点的值。

5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同形态有哪些？

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、假设以二叉链表作为二叉树存储结构，其类型定义如下：

typedef struct node

{ char data;

struct node *lchild,*rchild;//左右孩子指针

}BinTNode,*BinTree;

写一函数，完成以下功能：

对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩子

设置为左孩子。

2、试设计将数组 A[0…n-1]中所有奇数移到所有偶数之前的算法。要求不另增

加存储空间且时间复杂度为O(n)。

数据结构试题1参考答案

一、1——5：DADAB 6——10：CCBDD

二、1——5：ⅹ√ⅹⅹ√ 6——10：√ⅹⅹⅹⅹ

三、 1、①f→prior， ②p→next→prior 2、10 15 12 3、顺序压缩 4、2(n-1)

5、129 6、n/2的最小整数 7、(p→lchild==NULL)&&(p→rchild==NULL)

8、0 9、n(n-1) 10、归并排序

四、1、 答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。

双链表 的删除时间复杂度为O(1)，单循环链表删除p 结点的时间复杂度为O(n)。

2、答案：（1）由于散列表的长度为12，则可选不超过表长的最大素数11作为除留余 数

法的模，则可得其散列函数为h(k)=k%11。

（2）若用线性探测法解决冲突，则可构造出散列表如下：

13 14 35 17 29 153

0 1 2 3 4 5 6 7 8 9 10

11

此时，其装填因子为6/12=1/2，若用链式法解决冲突，则其散列表为：

3、 答案：（1）无向图的邻接矩阵所有数值之和除以2，为边数。有向图邻接矩阵各行 数

值之和为总边数。邻接表表示无向图内部顶点个数除以 2，有向图内部顶 点个数。

（2）无向图中 I 行和 J 列的交叉点的值是否为 1。有向图 I 行 J 列交叉点或 I列和

J行交叉点的值为1。

（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数 值之和。

4答案：

5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。

具有3个结点的二叉树的形态为：5种形态，有左右之分。

6：答案：

五、1、 答案： void exchange(Bin Tree T)

{ if(T)

{ if(!T→lchild&&T→rchild)

{T→lchild= T→rchild;

T→rchild=NULL; }

exchange(T→lchild);

exchange(T→rchild); }}

2、 答案： int oddbefore(A,n)//将数组 A[0…n-1]中所有奇数移到所有偶数之前

int A[ ];

{ int c,i,j; i=0;j=n-1;//初始化 i、j

while(i

{while((A[i]%2==1)&&(i

i++;

while((A[i]%2==0)&&(i

j--;

if(i

{c=A[i];

A[i]=A[j]; A[j]=c; i++;

j--; } }

return(1)

} //oddbefore

数据结构试题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六项子工程组成， 这些工程之间有下列关系： P1

P3

表示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→data

t= 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→data

p=p→next;

q→next=p; }

数据结构试题3

一、单项选择题（每小题3分，共30分）

1、假设有 n个关键字，它们具有相同的Hash 函数值，用线性探测法把这 n个

关键字存入到Hash地址空间中要做（ ）次探测。

A、n

2

B、n(n+1) C、n(n+1)/2 D、n(n-1)/2

2、若有一个栈的输入序列是 1，2，3，…，n 输出序列的第一个元素是 n，则

第 i 个输出元素是（ ）。

A、n-i B、n-i-1 C、n-i+1 D、不确定

3、在一棵度为3的树中，度为 3的结点数为 2 个，度为2的结点数为 1个，

度为1 的结点树为2个，那么度为 0的结点数为（ ）。

A、4 B、5 C、6 D、7

4、在一个具有 n个结点的无向完全图中，包含有（ ）条边。

A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n

2

5、已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当

二分检索值为90的元素时，需（ ）次比较可检索成功。

A、 1 B、2 C、3 D、4

6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（ ）。

A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接选择排序

7、已知 8 个元素（34，76，45，18，36，54，92，65），按照依次插入结点的

方法生成一棵二叉排序树，该树的深度为（ ）。

A、4 B、5 C、6 D、7

8、设有一个10阶的对称矩阵 A，采用压缩存储方式以行序为主存储，a00为第

一个元素， 其存储地址为0，每个元素占有 1个存储地址空间，则a85的地

址为 （ ）。

A、13 B、33 C、17 D、32

9、设关键字序列为：3，7，6，9，8，1，4，5，2。进行排序的最小交换次数为

（ ）。

A、6 B、7 C、8 D、20

10、给定权的集合{15，3，14，2，6，9，16，17}，所构造出的哈夫曼树的带

权路径长度为（ ）。

A、129 B、219 C、189 D、229

二、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题１分，

共１０分）

1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结

点进行查找任何一个元素。 （ ）

2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树

的先序遍历中的最后一个结点。 （ ）

3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空

间大小与图中结点的个数有关，而与图的边数无关。 （ ）

4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突

的方法两个方面。 （ ）

5、因为算法和程序没有区别，所以在数据结构中二者是通用的。 （ ）

6、进栈操作 push(x,s)作用于链接栈时，无须判满。 （ ）

7、稳定排序算法是最好的。 （ ）

8、二叉搜索树的左、右子树都是二叉搜索树。 （ ）

9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。 （ ）

10、表中的每一个元素都有一个前驱和后继元素。 （ ）

三、填空题（每小题2分，共20分）

1、在散列表(Hash)查找中，评判一个散列函数优劣的两个主要条件是_______和

________。

2、设根结点处在第一层，那么具有 n 个结点的完全二叉树，其高度为_____。

3、快速排序方法的最坏时间复杂度为______，平均时间复杂度为___。

4、给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始

堆表为_________。

5、设图 G 的顶点数为 n，边数为 e，各顶点的度数为 D(Vi)，则e=________。

6、将5个不同的数据进行排序，至少需要比较_____次，至多需要比较_______

次。

7、二分折半查找的查找速度一般比顺序查找的速度快，设有100个元素，用二

分折半查找时，最大比较次数是____，最小比较次数是_____。

8、由 a，b，c3 个结点构成的二叉树，共有_________种不同的结构。

9、在一棵高度为 h 的平衡二叉树中，至少含有________个结点，最多含有 2

h

-1

个结点。

10、在一个单链表中删除*p 结点，应执行如下操作 ：

q=p→next;

p→data=p→next→data;

p→next=________;

free(q);

四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头

指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？

2、假设用于通讯的电文仅有 8 个字母组成，字母在电文中出现的频率分别为：

7， 19，2，6，32，3，21，10。试用这8个频率值构造哈夫曼树，并画出该

哈夫曼所对应的森林。

3、已知一个长度为12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，

Sep， Oct，Nov，Dec）：

（1）构造最价二叉排序树；

(2)试求在等概率情况下对此二叉排序树进行折半检索时检索成功的平均长

度。

4、对于下图，试给出：

（1）每个顶点的入度和出度； （2）邻接矩阵；

（3）逆邻接表； （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、假设以二叉链表作为二叉树存储结构，其类型定义如下：

typedef struct node

{ char data;

struct node *lchild,*rchild; //左右孩子指针

}BinTNode,*BinTree;

写一函数，完成以下功能：

对二叉树中每个结点，如果其左孩子为空（右孩子不为空），则将其右孩

子设置 为左孩子。

2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。

试编写 一个删除表中所有值大于 min且小于 max的元素 （若表中存在

这样的元素） 的算法。

数据结构试题3答案

一、1——5：CCCAB 6——10：DCBAD

二、1——5：ⅹ√√√ⅹ 6——10：√ⅹ√ⅹⅹ

三、1、① 值均匀分布于表空间以减少冲突 ② 函数尽可能简单以方便计算

2、logn的最小整数+1 3、①O(n 2 ) ②O(nlogn)

4、(31 38 44 56 75 80 55 63) 或(80 75 55 56 63 44 31 38)

5、0.5*D(Vi)之和(i…n) 6、①4 ②10

7、①7 ②1 8、5 9、h 10、p→next→next

四、1、答案： 在单链表中不能删除，而在双链表和单循环链表中可以删除 p

结点。双链表的删除时间复杂度为O(1)，单循环链表删除p 结点的时

间复杂度为O(n)。

2、答案： （哈夫曼树有多种形态，不是唯一的。 ）

（1）哈夫曼树为：

（2）哈夫曼树所对应的森林为：

3、答案：（1）

（2）在等概率情况下检索成功的平均检索长度：

ASL=（1*1+2*2+3*4+4*4+5*1）/12=38/12=19/6

3、答案：（1）各个顶点的入度和出度如下：

顶点：1 2 3 4 5 6

入度：2 2 1 3 2 1

出度：1 2 3 0 3 2

（2）邻接矩阵为： （3）逆邻接表为：

（4）、强连通分量有如下3个：

5、答案：快速排序需要的辅助空间与辅助栈的深度有关，平均情况下为O(logn),

最坏情况下需要 O(n)；插入排序和堆排序只需要一个元素大小的辅助空间

在元素交换时用,为O(1)；而自然两路归并排序需和待排序数组同样大小的

辅助空间，为O(n)，所以自然两路归并排序所需的辅助空间最大，快速排序

次之，插入排序和堆排序最小。

6、答案：

五、1、答案： void exchange(Bin Tree T)

{ if(T)

{ if(!T→lchild&&T→rchild)

{ T→lchild= T→rchild;

T→rchild=NULL; }

exchange(T→lchild);

exchange(T→rchild); } }

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→data

p=p→next;

q→next=p;}

数据结构试题4

一、单项选择题（每小题3分，共30分）

1．一般情况下将递归算法转换为等价的非递归算法应设置_____. ( )

[A] 堆栈 [B] 队列 [C] 数组 [D] 堆栈或队列

2．设队列的输入序列是1、2、3、4，则只有_____是其出队序列。 ( )

[A] 1234 [B] 2134 [C] 1432 [D] 4312

3．C语言中要保存10个字符的字符串,至少需要声明大小为___的一维数组。

( )

[A] 10 [B] 。 [A] F(0)=0 [B] F(1)=1 [C] F(0)=1 [D] F(n)=n

4．若一棵哈夫曼树有20个度为2的结点，则它共有_____个叶结点。 ( )

[A] 19 [B] 21 [C] 23 [D] 25

5．如果T2是由有序树T转换而来的二叉树，那么T中结点的后根序列就是

T2中结点的________。 （ ）

[A] 先根序列 [B] 中根序列 [C] 后根序列 [D] 层次序列

6. 有向图中所有顶点的入度之和等于所有顶点的出度之和的____倍。 ( )

[A] 1 [B] 2 [C] 1/2 [D] 不一定

7．递归函数F(n)=F(n-1)+n+1(n>1)的递归出口是_____. ( )

[A]F(0)=0 [B]F(1)=1 [C]F(0)=1 [D]F(n)=n

8．在下列算法中，______算法可能出现以下情况：在最后一趟开始之前，所有

的元素都不在其最终的位置上。 ( )

[A] 堆排序 [B] 冒泡排序 [C] 插入排序 [D] 快速排序

9．在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为____。 ( )

[A] O(1) [B] O(log2n) [C] O(n

2

) [D] O(n)

10．具有四层结点AVL树至少有_______个结点。 ( )

[A] 10 [B] 9 [C] 8 [D] 7

二、填空题（每小题2分，共20分）

1.在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着的

__________、__________和_____________的联系。

2．在线性表的单链接存储中，指向下一结点的指针为next。若一个元素所在结

点的地址为p，则其后继结点的地址为____________，若假定p为一个数组a

中的下标，则其后继结点的下标为___________。

3. 栈又称为______________表，队列又称为____________表。

4. 后缀表达式“4 5 + 3 * 2 4 + * ”的值为____________。

5. 一棵深度为5的满二叉树中的结点数为______个,一棵深度为3的满四叉树中

的结点数为_________个。

6. 对于一棵含有40个结点的理想平衡树,它的高度为___________。

7. 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们

的位置，此种排序方法叫做________排序；每次使两个相邻的有序表合并成

一个有序表的排序方法叫做________排序。

8. 当从一个小根堆中删除一个元素时，需要把_________元素填补到________位

置，然后再按条件把它逐层________调整。

9. 对于一个具有n个顶点的图,若采用邻接矩阵表示，则矩阵大小为_________。

10. 向一棵 B—树插入元素的过程中，若最终引起树根结点的分裂，则新树的高

度比原树增________；从一棵 B—树删除元素的过程中，若最终引起树根

结点的合并，则新树的高度比原树减__________。

三、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题 １分,

共１０分）

1.给出不同输入序列建造二叉排序树，一定得到不同二叉排序树 。 ( )

2.有向图的邻接表和逆邻接表中的结点数一定相同。 ( )

3.图G的拓扑序列唯一，则其弧数必为 n-1(其中n为G的顶点数)。 ( )

4.在索引顺序文件中插入新的记录时，必须复制整个文件。 ( )

5.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。 ( )

6.对n个记录进行冒泡排序，在最坏情况下所需要的时间是O(n

2

)。 ( )

7. 在线性结构中，每个结点都有一个直接前驱和一个直接后继。 ( )

树的任何子树都是AVL树。 ( )

9. B＋树既适于随机检索，也适于顺序检索。 ( )

10.两个字符串相等的充要条件是两个串包含的字符相同。 ( )

四、简答题（每题10分，共60分）

1. 说明数组和链表的区别，各有何优缺点？

2. 已知序列（17，18，60，40，7，32，73，65，85），请给出采用起泡排序法

对该序列作升序排序时的每一趟的结果。

3．邻接矩阵表示图时，若图中有1000个顶点，500条边，则形成的邻接矩阵有

多少个元素？有多少个非零元素？是否为稀疏矩阵？

4．简述二叉排序树的概念，并按给定的输入序列：

25、13、15、31、7、20、37

构造一棵二叉排序树。

5．一棵二叉树的前序、对称序和和后序序列分别如下，其中有一部分未显示出

来，试求空格处内容，并画出该二叉树对应的森林。

前 序：__B__F__ICEH__G

对称序：D__KFIA__EJC__

后 序: __K__FBHJ__G__A

6．有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、

10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结

点的权)，求出每个字符的huffman编码。

五、算法设计题（每题15分，共30分）

说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。

1．已知长度为n的线性表A采用顺序存储结构，写一算法，删除该线性表中所

有值为 item的数据元素，并给出算法的时间复杂度。

2．设计一个算法，统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所

有顶点的度。

数据结构试题4答案

一、1. A 2.A 3. B 4. B 5. B 6.A 7. B 8. C 9. D 10.D

二、1. 1:1 1:N M:N （或者 一对一 1对多 多对多）

2. p->next a[p].next 3. 后进先出 先进先出 4. 162

5. 31 21 6. 6 7. 交换 二路归并（或归并）

8. 堆尾 堆顶 向下 9. n

2

10. 1 1

三、1．X 2.√ 3. √ 4. X 5. X 6.√ 7.X 8.√ 9.X 10.X

四、答案：区别：数组占用连续的内存空间，链表不要求结点的空间连续。

各有何优缺点：（1） 插入和删除操作。数组插入和删除需移动数据元素，

链表插入和删除不移动数据元素，链表比数组易于实现插入和删除操作；

（2） 在空间占用方面，数组优于链表；

（3） 在数据存取方面，数组是随机存取方式，而链表是顺序存取方式。

2.答案：采用起泡排序法排序的各趟结果如下：

初 始：17，18，60，40，07，32，73，65，85

第一趟：17，18，40，07，32，60，65，73，85

第二趟：17，18，07，32，40，60，65，73，85

第三趟：17，07，18，32，40，60，65，73，85

第四趟：07，17，18，32，40，60，65，73，85

第五趟：07，17，18，32，40，60，65，73，85

第五趟无元素交换，排序结束。

3．答案：邻接矩阵有1 000 000个元素。

对于有向图，有500个非零元素；对于无向图，有1 000个非零元素。

此邻接矩阵是稀疏矩阵。

4．答案：如果一棵二叉树的每个结点对应于一个关键码，且每个结点的左子树

中所有结点的关键码值都小于该结点的关键码值，而右子树中所有结点的关

键码值都大于该结点的关键码值，称此二叉树为二叉排序树。

5．答案：前 序:A B D F K I C E H J G

对称序:D B K F I A H E J C G

后 序: D K I F B H J E G C A

对应的森林为：

6.答案:

相应的哈夫曼编码为： :001 b:10 c:01 d:000 e:11.

五、1答案： 算法的 ADL描述如下：

算法DEL(A,n,item)

i←1 WHILE(i<=n) DO

IF (A[i]=item) THEN

{ FOR j=i+1 TO n DO

A[j-1] ← A[j]

n←n-1 }

ELSE

i←i+1

算法的时间复杂度为O(n 2 )

2．答案：假设邻接矩阵为 adjacency（二维数组），顶点的度保存在一维数组 A

中。

算法的 ADL描述如下：

[初始化]

FOR i=1 TO n DO

A[i]←0

FOR i=1 TO n DO

FOR j=1 TO n DO

IF adjacency[i,j]=1 THEN

A[i]←A[i]+1

数据结构试题5

一、单项选择题（每小题3分，共30分）

1．线性表是具有 n个_____的有限序列。 ( )

[A] 表元素 [B] 字符 [C] 数据元素 [D] 信息项

2．若长度为 n 的线性表采用顺序存储结构，在第i个位置插入一个元素的算法

的时间复杂度是________ 。 ( )

[A] O(log2n) [B] O(n 2 ) [C] O(nlog2n) [D] O(n)

3．二维数组 A 中每个元素的长度为 3 个字节，行下标从 0 到 9，列下标从0

到11，则存放该数组至少需要______个字节。 ( )

[A] 100 [B] 270 [C] 360 [D] 340

4．若一棵满二叉树有2047个的结点，则该二叉树中叶结点个数为_____。( )

[A] 512 [B] 1024 [C] 2048 [D] 4096

5．如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2

中结点的______。 ( )

[A] 先根序列 [B] 中根序列 [C] 后根序列 [D] 层次序列

6. 无向图中所有顶点的度数之和等于所有边的数目的_____倍。 ( )

[A] 1 [B] 2 [C] 1/2 [D] 不一定

7．递归函数F(n)=F(n-1)+n+1(n>0)的递归出口是_______。 ( )

[A] F(0)=0 [B] F(1)=1 [C] F(0)=1 [D] F(n)=n

8. 排序趟数与序列原始状态有关的排序方法是______法。 ( )

[A] 插入排序 [B] 选择排序 [C] 冒泡排序 [D] 快速排序

9．采用直接选择排序，比较次数和移动次数分别是_____。 ( )

[A] O(n),O(log

2

n) [B] O(log

2

n),O(n

2

)

[C] O(n

2

), O(n) [D] O(nlog

2

n),O(n)

10．从n个结点的二叉搜索树中查找一个元素时，最差时间复杂度为____。 ( )

[A] O(1) [B] O(log2n) [C] O(n 2 ) [D] O(n)2

二、填空题（每小题2分，共20分）

1.数据的逻辑结构被分为___________、____________和______________。

2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为

_________,在表尾插入元素的时间复杂度为__________。

3.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、

________和_______三项。

4.当用长度为N的数组顺序存储一个栈时，假定用top = =N表示栈空，则表示栈

满的条件为_________________。

5.假定一棵三叉树的结点个数为50， 则它的最小深度为__________,最大深度为

_________。 6.二分查找过程所对应的判定树既是一棵________，又是一棵

_________。

7.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一

级20个记录的索引，则一级索引表的长度为_________，二级索引表的长度为

_________。

8.在归并排序中，进行每趟归并的时间复杂度为_______，整个排序过程的时间

复杂度为_______,空间复杂度为________。

9.从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明

_______，若元素的值小于根结点的值，则继续向_______查找，若元素的值大

于根结点的值，则继续向________查找。

10.对于一个具有n个顶点和e条边的连通图，其生成树中顶点数和边数分别为

________和_ __________。

三、判断题 （认为对的，在题后的括号内打“√”，错的打“ⅹ”，每小题 １分，

共１０分）1.同一个逻辑结构可以有几种不同的存储映象方法。

（ ）

2.对单链实现的队列作出队操作，不会改变尾指针R的值。 （ ）

3.对称表的每个结点指针字段指向该结点的后继结点。 （ ）

4.如果某种排序方法是不稳定的，则该方法没有实际应用价值。 （ ）

5.对n个记录进行起泡排序，最坏情况下所需要的时间为0（n）。 （ ）

6.在散列表中，负载因子的值越大则存元素时发生碰撞的可能性越大。 （ ）

7.二叉树可以为空。 （ ）

8.前序周游序列和中序周游序列不能唯一确定一棵二叉树。 （ ）

9.一棵树中的叶结点数一定等于与其对应的二叉树中的叶结点数。 （ ）

10.广义表中原子数即为广义表的长度。 （ ）

四、简答题（每题10分，共60分）

1.设有初始的无序序列为{98,65,38,40,12,51,100,77,26,88},给出对其进行归并排

序(升序)的每一趟的结果。

2．已知一个散列表如下图所示：

35 20 33 48 59

0 1 2 3 4 5 6 7 8 9 10 11 12

其散列函数为h(key)=key%13, 处理冲突的方法为双重散列,

探查序列为： hi=(h(key)+*h1(key))%m =1,2,…，m－1 （m=13）

其中 h1(key)=key%11+1

回答下列问题：

（1）对表中关键字 35，20，33 和 48 进行查找时，所需进行的比较次数各为

多少？

（2）该散列表在等概率查找时查找成功的平均查找长度为多少？

3．从一棵空的二叉树开始，按给定的输入序列：40、28、06、72、100、03、 54、

01、80、91、38，构成一棵二叉排序树，然后删除结72，分别画出该二叉排

序树及删除结点72后的二叉树。

4.二叉树结点采用顺序存储结构，如下图所示。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

e f c j i

a d g h b

（1）写出前序、对称序和后序周游的结果。

（2）画出此二叉树对应的森林。

5.回答下列关于堆的一些问题：

（1）堆的定义是什么？

（2）存储表示是顺序的，还是链式的？

（3）设有一个最小堆,其具有最小值、最大值的元素分别可能在什么地方？

6.若每个指针需4个字节，每个顶点的序号占2个字节，每条边的权占2个字节，

则下图的邻接矩阵和邻接表两种表示法中哪种所需的存储空间较少，为什么？

画出该图从顶点1出发的最小生成树。

五、算法设计题（每题15分，共30分）

说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。

1.已知非空单链表第一个结点的指针为 list，写一算法,删除该链表的第 i 个结

点，并给出算法的时间复杂度。

2．设计一个算法，统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所

有顶点的度。

数据结构试题5答案

一、1. C 2. D 3.C 4. B 5.A 6. B 7.A 8. C 9. C 10.D

二、1. 线性结构 树结构 图结构（次序无先后） 2．O（n） O（1）

3．行号 列号 元素值（次序无先后） 4．top= =0

5．5 50 6. 二叉搜索树 理想平衡树 （次序无先后） 7. 500 25

8. O(n) O(nlog2n) O(n) 9. 查找成功 左子树 右子树 10. n n-1

三、1. √ 2.X 3. X 4. X 5.X 6.√ 7.√ 8. X 9. X 10.X

四、1. 初始无序序列：98 65 38 40 12 51 100 77 26 88

｛98｝｛65｝｛38｝｛40｝{12}｛51｝｛100｝｛77｝｛26｝｛88｝

第一次归并：{65 98}｛38 40｝｛12 51｝｛77 100｝｛26 88｝

第二次归并：｛38 40 65 98｝｛12 51 77 100｝｛26 88｝

第三次归并：｛12 38 40 51 65 77 98 100｝｛26 88｝

第四次归并：｛12 26 38 40 51 65 77 88 98 100｝

2．(1) 对关键字35、20、33和48进行查找的比较次数为３、２、１、１；

(2) 平均查找长度：

3. 二叉排序树：

4.（1） 前 序：eabcdjfghi

对称序：abcdjefhgi

后 序：bcjdahigfe

（2）对应的森林为：

5．（1）堆是 n个元素的有限序列 K1，K2，… , KN，且满足以下条件:

K

i

<= K

2i

且 Ki <= K

2i+1

I=1,2,…, n/2 （最小堆）

或 K

i

>= K

2i

且 Ki >= K

2i+1

I=1,2,…, n/2 （最大堆）

（2）因为完全二叉树采用顺序存储更加有效，所以堆应采用顺序存储结构。

（3）最小堆的最小值元素必在堆顶，最大值的元素只有在叶结点上。

6.相邻矩阵表示需6个结点的顺序表保存顶点的数据，及6*6的矩阵来表示顶点

间的相邻

关系,上图所示为无向图，只要存储下三角(或上三角)部分即可,所以所需空间

为： 2*6+2*21=54（字节）

邻接表表示需6个单元的结点表和2*9个单元的边表，其中结点表每个单元占

6字节，边表每个单元占8字节，所以所需空间为：

6*6+8*2*9=180（字节）

所以相邻矩阵所需空间较少。

最小生成树：

五、1、算法的 ADL描述如下：

算法DEL(list,i)

q←list

IF (I=1) THEN

list←next(list)

ELSE

{ FOR j=1 TO i-1 DO

{ r←q q←next(q)

IF (q=NULL) THEN

{ PRINT(“链表中不存在第 i个结点”)

RETURN } }

next(r)←next(q)6 }

DELETE q

算法的时间复杂度为O(n)

2．假设邻接矩阵为 adjacency （二维数组）， 顶点的度保存在一维数组A中。

算法的ADL描述如下：

[初始化]

FOR i=1 TO n DO

A[i]←0

FOR i=1 TO n DO

FOR j=1TO n DO

IF adjacency[i,j]=1 THEN

A[i]←A[i]+1