数据结构考试试题.docx
《数据结构考试试题.docx》由会员分享，可在线阅读，更多相关《数据结构考试试题.docx（26页珍藏版）》请在冰点文库上搜索。
数据结构考试试题
数据结构考试试题
数据结构辅导试题一
一、简答问题：
1．四类数据结构
2．线性结构与非线性结构有何差别？
3．简述算法的定义与特性。
4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？
5．
二、判断正误：
（每小题1分，共5分）正确在（）内打√，否则打。
1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树：
若它的左子树非空，则根结点的值大于其左孩子的值，
若它的右子树非空，则根结点的值大于其右孩子的值。
2．（）索引顺序表的特点是块内可无序，块间要有序。
3．（）子串是主串中任意个连续字符组成的序列。
4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。
5．（）快速排序的枢轴元素可以任意选定。
三、单项选择题：
（每小题1分，共4分）
1．栈S最多能容纳4个元素。
现有6个元素按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列
A）E、D、C、B、A、FB）B、C、E、F、A、D
C）C、B、E、D、A、FD）A、D、F、E、B、C
2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：
A、98B、99C、50D、48
3.对下列关键字序列用快速排序法进行排序时，速度最快的情形是：
A）{21、25、5、17、9、23、30}B）{25、23、30、17、21、5、9}
B）{21、9、17、30、25、23、5}D）{5、9、17、21、23、25、30}
4.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。
与森林F对应的二叉树根结点的右子树上的结点个数是：
A）M1B）M1+M2C）M3D）M2+M3
四、填空题：
（每小题2分,共20分）
1．设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P<=M）,为使函数具有较好性能，P应选
2．N个结点的二叉树采用二叉链表存放，共有空链域个数为
3．单链表与多重链表的区别是
4．在各种查找方法中，平均查找长度与结点个数无关的是
5．深度为6（根层次为1）的二叉树至多有个结点。
6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是
7．在一个单链表中p所指结点之后插入s所指结点时,应执行
s->next=和p->next=的操作.
8．广义表（（a,b）,c,d）的表头是,表尾是
9．循环单链表LA中，指针P所指结点为表尾结点的条件是
10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。
五、构造题：
（每小题5分，共25分）
1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。
2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。
3．有一组关键字{50，52，85，22，96，17，36，55}，请用快速排序，写出第一趟排序结果。
4．已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。
5．画出8个结点的折半判定树。
六、算法设计题：
（每小题15分，共30分）（仅要求给出子程序）
1．编写算法，判断带头结点的双向循环链表L是否对称。
（15分）
对称是指：
设各元素值a1,a2,...,an,则有ai=an-i+1，
即指：
a1=an，a2=an-1。
。
。
。
。
。
。
结点结构为：
prior
data
next
2．二叉排序树T用二叉链表表示，其中各元素均不相同。
（1）写出递归算法，按递减顺序打印各元素的值。
（10分）
（2）写出完成上述要求的非递归算法。
（5分）
《数据结构》试卷参考答案
一、简答问题：
（每小题4分，共16分）
1．集合结构、线性结构、树形结构、网状结构
2． 线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一对多或多对多关系。
3． 解决特定问题的有限指令序列。
有限性、确定性、可行性、有0个或多个输入数据、有1个或多个输出结果。
4． 堆排序。
因为一趟堆排序排定一个元素，只需进行前10趟堆排序就可以了。
其它排序方法均需进行完全排序。
二、判断正误：
（每小题1分，共5分）
正确在（ ）内打√，否则打。
1.（） 2.（√） 3.（√） 4.（） 5.（√）
三、单项选择题：
（每小题1分，共4分）
1．C） 2．A） 3. A） 4. D）
四、填空题：
（每小题2分,共20分）
1． 97 2. n+1 3.链域数目不同
4.哈希查找法 5.26–1 6.1168
7.p->next 、 s 8.（a,b） 、 （c,d）
9.P->next==LA 10.直接插入
五、构造题：
（每小题5分，共25分）
1．
2．
0
1
2
3
4
5
6
7
8
9
10
K
TA
BA
M
D
CI
X
TN
I
ASL=20/9
0
1
2
3
4
5
6
7
8
9
10
ASL=15/9
3．
{36，17，22，50，96，85，52，55}
4．
WPL=11×2+6×2+9×2+5×3+2×4+3×4
=87
[注]：
哈夫曼树的左右子树可以互换。
5．
[注]：
如果求中点时采用向上取整，则二叉树的形态为左子树偏长。
六、算法设计题：
（每小题15分，共30分）
（仅要求给出子程序）
1．[解答]：
intjudge（DLinkListL）{
p=L->next; q=L->prior;
while（p!
=q）
{if（p->data!
=q->data）return0;
if（p->next==q）return1;
p=p->next;
q=q->prior;
}
return1;
}
[注]：
可以不用返回值，而用打印信息。
2．[解答]：
（1）
voidprint_1（BiTreeT）{
if（T!
=NULL）
{print_1（T->RChild）;
printf（“%c”,T->data）;
print_1（T->LChild）;
}
}
（2）
void Print_2（BiTreeT）
{InitStack（&S）;
p=T;
while（p!
=NULL||!
IsEmpty（S））
{while（p!
=NULL）
{Push（&S, p）;
p=p->RChild;
}
if（!
IsEmpty（S））
{Pop（&S, &p）;
printf（“%c”, p->data）;
p=p->LChild;
}
}
}
数据结构辅导试题二
一、简答题：
（每小题3分，共15分）
1.什么情况下二叉排序树的查找性能较好什么情况下二叉排序树的查找性能最差
2.
3.比较顺序表与单链表的优缺点。
4.请写出栈的链式存储结构的类型定义。
5.在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。
6.简述参数传递的主要方式及其特点。
二、判断正误：
（每小题1分，共5分）
正确在（）内打√，否则打。
（）
（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。
（）
（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。
（）（3）在一个小根堆中，具有最大值的元素一定是叶结点。
（）（4）索引顺序表的特点是块间可无序，但块内一定要有序。
（）（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。
三、单项选择题：
（每小题1分，共5分）
1．对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:
A）顺序表B）用头指针表示的单循环链表
C）用尾指针表示的单循环链表D）单链表
2．假设以第一个元素为分界元素，对字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）进行快速排序，则第一次划分的结果是：
A）（A,C,D,F,H,M,P,Q,R,S,X,Y）B）（A,F,H,C,D,P,M,Q,R,S,Y,X）
C）（F,H,C,D,P,A,M,Q,R,S,Y,X）D）（P,A,M,F,H,C,D,Q,S,Y,R,X）
3．下面是三个关于有向图运算的叙述：
（1）求有向图结点的拓扑序列，其结果必定是唯一的
（2）求两个指向结点间的最短路径，其结果必定是唯一的
（3）求AOE网的关键路径，其结果必定是唯一的
其中哪个（些）是正确的？
A）只有
（1）B）
（1）和
（2）C）都正确D）都不正确
4．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为:
A）4B）5C）6D）7
5.以下关于广义表的叙述中,正确的是：
A）广义表是由0个或多个单元素或子表构成的有限序列
B）广义表至少有一个元素是子表
C）广义表不能递归定义D）广义表不能为空表
四、填空题：
（每小题2分,共20分）
1．一棵含有101个结点的完全二叉树存储在数组A[1..101]中,对1≤k≤101,若A[k]是非叶结点,则k的最小值是:
，k的最大值是:
。
2.设s=’YOUAREJUDGINGITRIGHTORWRONG’，顺序执行下列操作：
SubString（sub1,s,1,8）;SubString（sub2,s,20,5）;StrCat（sub1,sub2）;则最后sub1的值为：
。
3.若一个算法中的语句频度之和为T（n）=3720n+4nlogn，则算法的时间复杂度为________________。
4．广义表（（（（a）,b）,c）,d）的表头是，表尾是。
5．已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：
将累加。
6．要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为t,则应执行操作：
和。
7.用带头结点的循环链表表示的队列,若只设尾指针rear,则队空的条件是。
8．已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]的存储地址是1024,则A[6][18]的地址是
9．在表示二叉树的二叉链表中,共有个空链域。
10．n个顶点的连通无向图至少有条边，至多有条边。
五、构造题：
（每小题6分，共30分）
1．已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，给出对应的二叉树。
2．已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括主对角线元素），其他元素均为1。
请画出该图，并给出其邻接表。
3．给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。
4．图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。
图2
5．对关键字序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列。
请写出排序过程中得到的初始堆和一趟排序后的序列状态。
六、算法设计题：
（共25分）
1．设有一个由正整数组成的单链表L（含头结点），编写完成下列功能的算法：
找出最小值结点P，若最小值是奇数，则删除结点P。
[15分]
2．已知树用孩子兄弟链表存储，root指向根结点。
编写算法，逐层遍历这棵树。
[10分]
《数据结构》试卷参考答案
一、简答题：
（每小题3分，共15分）
1.前驱与后继之间通常为一对多或多对多的关系。
2.顺序表优点：
随机查找，存储密度大
顺序表缺点：
插入、删除不便，静态分配，表长固定
单链表优点：
插入、删除方便，动态分配，表长灵活
单链表缺点：
查找不便，存储密度小
3.关键字相同的两个记录，排序前后其先后顺序不变。
4.typedefstructnode{
ElemTypedata;
structnode*next;
}*LinkStack;
5.当二叉排序树接近平衡二叉树或完全二叉树时查找性能较好，当二叉排序树为单边单枝二叉树时查找性能最差。
二、判断正误：
（每小题1分，共5分）
正确在（）内打√，否则打。
（）
（1）（）
（2）（√）（3）（）（4）（）（5）
三、单项选择题：
（每小题1分，共5分）
1．C）2．C）3．D）4．B）5.A）
四、填空题：
（每小题2分,共20分）
1．12.’YOUARERIGHT’
3.O（nlogn）4．（（（a）,b）,c），（d）
5．i列元素6．t->next=p->next，p->next=s
7.rear->next==rear8．1300
9．n+110．n-1
五、构造题：
（每小题6分，共30分）
1．
2．
3．
或：
WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2
=207
[注]：
哈夫曼树的左右子树可以互换。
4．
[解1]：
[解2]：
[注]：
边上的权值可以省略。
5．
初始堆：
05，23，16，58，94，72，61，87
一趟排序后的序列状态：
87，23，16，58，94，72，61，05
筛成堆后为：
16，23，61，58，94，72，87，05
[注]：
如果采用大根堆，应适当减分。
六、算法设计题：
（共25分）
3．[15分]
voidmin（LinkListL）{
if（L->next==NULL）return;
q=L;r=L->next;m=r->data;
while（r->next!
=NULL）
{if（r->next->data{m=r->next->data;q=r;}
r=r->next;
}
p=q->next;
if（m%2==1）{q->next=p->next;free（p）;}
}
4．[10分]
voidlayer（CSTreeroot）{
InitQueue（&Q）;EnterQueue（&Q,root）;
while（!
Empty（Q））
{DelQueue（&Q,&p）;visit（p）;
p=p->FirstChild;
while（p!
=NULL）
{EnterQueue（&Q,p）;p=p->NextSibling;}
}
}
数据结构辅导试题三
一、简答题（15分，每小题3分）
1.简要说明算法与程序的区别。
2.在哈希表中，发生冲突的可能性与哪些因素有关为什么
3.
4.说明在图的遍历中，设置访问标志数组的作用。
5.说明以下三个概念的关系：
头指针，头结点，首元素结点。
6.在一般的顺序队列中，什么是假溢出怎样解决假溢出问题
7.
二、判断题（10分，每小题1分）
正确在括号内打√，错误打×
（）
（1）广义表（（（a）,b）,c）的表头是（（a）,b），表尾是（c）。
（）
（2）在哈夫曼树中，权值最小的结点离根结点最近。
（）（3）基数排序是高位优先排序法。
（）（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。
（）（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：
p->next=s;s->next=p->next;
（）（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。
（）（7）数组元素的下标值越大，存取时间越长。
（）（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
（）（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。
（）（10）长度为1的串等价于一个字符型常量。
三、单项选择题（10分,每小题1分）
1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。
这是哪种排序方法的基本思想？
A、堆排序B、直接插入排序C、快速排序D、冒泡排序
2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：
A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0
C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0
3．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：
A.head->priro==NULLB.head->next==NULL
C.head->next==headD.head->next->priro==NULL
4.在顺序表（3,6,8,10,12,15,16,18,21,25,30）中，用折半法查找关键码值11，所需的关键码比较次数为：
A）2B）3C）4D）5
5.以下哪一个不是队列的基本运算？
A）从队尾插入一个新元素B）从队列中删除第i个元素
C）判断一个队列是否为空D）读取队头元素的值
6.在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：
A）n–i+1B）n–iC）iD）i–1
7．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为:
A）顺序表B）用头指针表示的循环单链表
C）用尾指针表示的循环单链表D）单链表
8．对包含n个元素的哈希表进行查找，平均查找长度为：
A）O（log2n）B）O（n）C）O（nlog2n）D）不直接依赖于n
9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点
进行编号，根结点编号为1，则编号最大的非叶结点的编号为：
A、48B、49C、50D、51
10．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：
A）3 B）2C）4D）5
四、填空题（10分，每空1分）
1．填空完成下面一趟快速排序算法：
intQKPass（RecordTyper[],intlow，inthigh）
{x=r[low]；
while（low{
while（low=x.key）
high--；
if（low{r[]=r[high]；low++;}
while（lowlow++;
if（low{r[]=r[low]；high--;}
}
r[low]=x；returnlow;
}
2.假设用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加入队列时，需执行下面语句：
；；R=S；
3．通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。
4．已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是：
5．高度为h的完全二叉树最少有个结点。
五、构造题（20分）
1．（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。
DS=（D,R）
D={a,b,c,d,e,f,g}
R={T}
T={,,,,,,
,,,,,}
2．（6分）对以下关键字序列建立哈希表：
（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为H（K）=（K中最后一个字母在字母表中的序号）MOD7。
用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下查找成功的平均查找长度。
3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53，87）调整为大根堆。
4．（4分）已知权值集合为：
{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。
六、算法分析题（10分）
阅读下面程序，并回答有关问题。
其中BSTree为用二叉链表表示的二叉排序树类型。
（1）简要说明程序功能。
（5分）
（2）n个结点的满二叉树的深度h是多少（
（3）3分）
（4）假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。
（2分）
intProc（BSTree*bst,KeyTypeK）
{BSTreef,q,s;
s=（BSTree）malloc（sizeof（BSTNode））;
s->key=K;s->lchild=NULL;s->rchild=NULL;
if（*bst==NULL）{*bst=s;return1;}
f=NULL;q=*bst;
while（q!
=NULL）
{if（Kkey）
{f=q;q=q->lchild;}
else
{f
升级会员 