文档介绍：数据结构复****题答案
数据结构复****题答案
数据结构复****题答案
复****一）
一、选择题
1．下面关于线性表的叙述错误的是（ D ）.
ﻩA、 线性表采用顺序存储必须占用一片连续的存储空间
B、 线性表采用链式存储不必占用一片连续的存储空间
C、 线性表采用链式存储便于插入和删除操作的实现
D、 线性表采用顺序存储便于插入和删除操作的实现
2。设哈夫曼树中的叶子结点总数为ｍ，若用二叉链表作为存储结构,则该哈夫曼树中总共有（ B ）个空指针域。
A、 2m—1ﻩＢ、 2ｍ C、 2m＋１ﻩD、 ４m
3。设顺序循环队列Q[0：M—1］的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针Ｒ总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。
A、 R—F B、 F－R C、(R—F＋Ｍ)％ＭﻩD、（F－R+M）％M
,前序遍历序列为ＣABD，则后序遍历该二叉树得到序列为(A）。
Ａ、 ＢADC B、 BCDAﻩC、 CDABﻩＤ、CBDA
５。设某完全无向图中有n个顶点,则该完全无向图中有( A ）条边。
数据结构复****题答案
数据结构复****题答案
数据结构复****题答案
Ａ、 n（n-1）/2ﻩB、 n（n－1） C、 n2 ﻩD、 n2-1
6．设某数据结构的二元组形式表示为A=(D,R），D=｛０1，０2，03，04,05,06，07,08,0９｝，R＝｛ｒ}，r={<01，０2>,＜01，0３〉，〈01，04〉,<02，05〉,<02，06>,〈０３，07〉，〈0３,０8>，<0３,０9>｝，则数据结构A是( B ).
A、线性结构ﻩB、 树型结构ﻩC、 物理结构 D、图型结构
7．下面程序的时间复杂为( B )
fｏr（i=1,ｓ＝0; i＜＝n； ｉ＋＋） {ｔ=1；for(ｊ=1；j〈=ｉ；ｊ++） t=t＊j;s=s+t；}
ﻩA、 O(n） Ｂ、 O(n2) C、 O(n3）ﻩ D、 Ｏ（ｎ4）
8．设指针变量p指向单链表中结点Ａ,若删除单链表中结点Ａ,则需要修改指针的操作序列为（ A ）。
A、q=ｐ->neｘt；p－〉datａ=q－〉ｄata；p-＞neｘｔ＝q->nｅxt；ｆree（q）；
B、q=p-〉next；q—>ｄata=p－>ｄatａ；p->ｎext=q－>nｅxｔ;ｆreｅ（q)；
ﻩC、q=p—〉next;p-〉next＝q->nｅxｔ；free（q)；
ﻩD、q＝p-〉ｎexｔ;p->data＝q－〉daｔa;frｅｅ（q）；
９。设有ｎ个待排序的记录关键字,则在堆排序中需要( A )个辅助记录单元。
ﻩA、 1ﻩＢ、 nﻩＣ、 nlog２n D、 n2
10．设一组初始关键字记录关键字为（２0,１5,14，18，21，３６，４0，10),则以２0为基准记录的一趟快速排序结束后的结果为( A ）。
数据结构复****题答案
数据结构复****题答案
数据结构复****题答案
A、 1０，15，14，18，20,3６,40,21
Ｂ、 １0，１5,１4，1８,20,40，36,21
C、 10，1５，14，20,１8,４0,36,2l
D、 15，10,14,１8,20，36,40，21
二、填空题
为了能有效地应用HASH查找技术，必须解决的两个问题是（构造一个好的HASＨ函数）和（确定解决冲突的方法)。
下面程序段的功能实现数据ｘ进栈,要求在括号处填上正确的语句.
ｔypedef sｔruct ｛ｉnt s［１00］； iｎt tｏp；} ｓｑstａck;
void push（sｑｓｔacｋ &stack,iｎｔ x)
{
if (==m—１) printf(“overｆｌow”）;
eｌse ｛（ sｔacｋ。s[stacｋ。top]=ｘ ）；（ +＋） ;｝
｝
中序遍历二叉排序树所得到的序列是（有序)序列（填有序或无序）。
快速排序的最坏时间复杂度为( O（n2))，平均时间复杂度为( O（nlog2n））。
数据结构复****题答案
数据结构复****题答案
数据结构复****题答案
设某棵二叉树中度数为０的结点数为Ｎ0，度数为1的结点数为Ｎ１，则该二叉树中度数为2的结点数为（ Ｎ0—1)；若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有(２N0+Ｎ1）个空指针域.
设有向图G中有n个顶点e条有向边,所有的顶点入度数之和为d，则e和d的关系为（ｅ=ｄ）。
（中序）遍历二叉排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)。
设查找表中有1００个元素，如果