数据结构试题及答案10（材料）_十套数据结构试题答案
数据结构试题及答案10（材料）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“十套数据结构试题答案”。
《数据结构》自考复习思考试题
一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上()
A.操作的有限集合B.映象的有限集合 C.类型的有限集合D.关系的有限集合2.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为（）A.n-i+1
B.i C.i+1
D.n-i 3.若不带头结点的单链表的头指针为head，则该链表为空的判定条件是（）A.head==NULL
B.head->next==NULL C.head!=NULL
D.head->next==head 4.引起循环队列队头位置发生变化的操作是（）A.出队
B.入队
C.取队头元素
D.取队尾元素
5.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）A.2，4，3，1，5，6
B.3，2，4，1，6，5 C.4，3，2，1，5，6
D.2，3，5，1，6，4 6.字符串通常采用的两种存储方式是（）A.散列存储和索引存储
B.索引存储和链式存储 C.顺序存储和链式存储
D.散列存储和顺序存储
7.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为（）A.m
B.n-m C.n-m+1
D.n 8.二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为（）A.429
B.432 C.435
D.438 9.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是（）A.(e,f)
B.((e,f))C.(f)
D.()10.下列图示的顺序存储结构表示的二叉树是（）11.n个顶点的强连通图中至少含有（）A.n-1条有向边
B.n条有向边 C.n(n-1)/2条有向边
D.n(n-1)条有向边
12.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（）A.(19，23，56，34，78，67，88，92)
B.(23，56，78，66，88，92，19，34)C.(19，23，34，56，67，78，88，92)
D.(19，23，67，56，34，78，92，88)13.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为（）
A.4
B.5 C.8
D.9 14.由同一关键字集合构造的各棵二叉排序树（）A.其形态不一定相同，但平均查找长度相同
B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同
15.ISAM文件和VSAM文件的区别之一是（）A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘
二、填空题(本大题共10小题，每空2分，共20分)16.数据的逻辑结构在计算机存储器内的表示，称为数据的____________。17.删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。18.栈下溢是指在____________时进行出栈操作。
19.已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=″ABCDEFGHIJK″,t=″ABCD″,执行运算substr(s,strlen(t), strlen(t))后的返回值为____________。
20.去除广义表LS=(a1,a2,a3,„„，an)中第1个元素，由其余元素构成的广义表称为LS的____________。
21.已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。22.在有向图中，以顶点v为终点的边的数目称为v的____________。
23.当关键字的取值范围是实数集合时，无法进行箱排序和____________排序。24.产生冲突现象的两个关键字称为该散列函数的____________。
25.假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中____________。
三、解答题(本大题共4小题，每小题5分，共20分)26.假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式；
(3)设m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。
27.已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。28.画出下图所示有向图的所有强连通分量。
29.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。
四、算法阅读题(本大题共4小题，每小题5分，共20分)30.阅读下列算法，并回答问题：(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；(3)简述算法的功能。
void f30(SeqList*L, DataType x){
int i =0, j;
while(ilength && x>L->data［i］)i++;
if(ilength && x==L->data［i］){
for(j=i+1;jlength;j++)
L->data［j-1］=L->data［j］;
L->length--;
} else {
for(j=L->length;j>i;j--)
L->data［j］=L->data［j-1］;
L->data［i］=x;
L->length++;
} } 31.已知图的邻接表表示的形式说明如下：
#define MaxNum
//图的最大顶点数 typedef struct node {
int
adjvex;
//邻接点域
struct node *next;
//链指针域
} EdgeNode;
//边表结点结构描述 typedef struct {
char vertex;
//顶点域
EdgeNode
*firstedge;
//边表头指针 } VertexNode;
//顶点表结点结构描述 typedef struct {
VertexNode adjlist［MaxNum］;
//邻接表
int n, e;
//图中当前的顶点数和边数 } ALGraph;
//邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
typedef enum {FALSE, TRUE} Boolean;Boolean visited［MaxNum］;void DFSForest(ALGraph *G){
int i;
for(i=0;in;i++)visited［i］=
(1)
;
for(i=0;in;i++)if(!visited［i］)DFSTree(G,i);} void DFSTree(ALGraph *G, int i){
EdgeNode *p;
visited［i］=TRUE;
p=G->adjlist［i］.firstedge;
while(p!=NULL){
if(!visited［p->adjvex］){
printf(″<%c,%c>″,G->adjlist［i］.vertex,G->adjlist［p->adjvex］.vertex);
(2)
;
}
(3)
;
} } 32.阅读下列算法，并回答问题：
(1)假设数组L［8］={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L，8)后的L；(2)写出上述函数调用过程中进行元素交换操作的总次数。void f32(int R［］,int n){
int i,t;
for(i=0;i
while(R［i］!=i){
t=R［R［i］］;
R［R［i］］=R［i］;
R［i］=t;
} } 33.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：。请在空缺处填入适当内容，使其成为一个完整算法。void f33(LinkList L, LinkList H［］, int m){//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在int i,j;
LinkList p,q;
for(i=0;i
H［i］=
(1)
;
p=L->next;
while(p)
{
q=p->next;
j=p->key%m;
(2)
;
H［j］=p;
(3)
;
}
free(L);
}
五、算法设计题(本大题10分)34.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType;typedef struct node {
DataType data;
struct node *lchild, *rchild;
//左右孩子指针
struct node *parent;
//指向双亲的指针 } BinTNode;typedef BinTNode *BinTree;若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。
(1)就后继的不同情况，简要叙述实现求后继操作的方法；
(2)编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。数据结构标准答案
一、单项选择题 1.(B)2.(D)3.(A)4.(A)5.(D)6.(C)7.(C)8.(A)9.(B)10.(A)11.(B)12.(D)13.(C)14.(B)15.(C)
二、填空题(本大题共10小题，每空2分，共20分)16.存储结构 17.q = p->pre;q->pre->next = p;p->pre = q->pre;free(q);18.栈空
19.“DEFG” //注意双引号不能少 20.表尾
21.２^(I-2)+M/2 叶子结点． 22.入度 23.基数 24.同义词
25.已有m个同义词记录
三、解答题(本大题共4小题，每小题5分，共20分)26.(1)quelen == m(2)quelen == 0(3)(13quelen + m)% m 27.B
/
A F
/
E G
/
C
D 28.3个: a、bce、dfg 29.我们知道，对n个关键自序列进行一趟快速排序，要进行n-1次比较，也就是基准和其他n-1个关键字比较。
这里要求10次，而71)= 10，这就要求2趟快速排序后，算法结束。所以，列举出来的序列，要求在做partition的时候，正好将序列平分(1)4 1 3 2 6 5 7
或 4 1 3 7 6 5 2 或 4 5 3 7 6 1 2 或 4 1 3 5 6 2 7.......(2)自己列吧 :)
四、算法阅读题(本大题共4小题，每小题5分，共20分)30.(1)L=(3,7,11,14,15,20,51)(2)L=(4,7,14,20,51)(3)在顺序表L中查找数x, 找到，则删除x，没找到，则在适当的位置插入x，插入后，L依然有序.31.(1)FALSE //初始化为未访问
(2)DSFTree(G, p->adjvex);//从相邻结点往下继续深度搜索(3)p = p->next;//下一个未访问的相邻结点
32.(1)L = { 0, 1, 2, 3, 4, 5, 6, 7 };(2)5次
33.(1)NULL
//初始化
(2)p->next = H[ j ] //和下面一句完成头插法(3)p = q;
//继续遍历L
五、算法设计题(本大题10分)34.1)
a)*px 有右孩子，则其右孩子为其中序序列中的后继
b)*px 无右孩子，从*px开始回溯其祖先结点，找到第1个身份为左孩子的结点，找到，则该结点的父结点为*px的中序序列中的后继。找不到，则无后继。2)BinTNode * fintNext(BinTNode * px){ if(px-> rchild)return px->rchild;//*px 有右孩子
BinTNode *q, *qp;
q = px;while(qp = q->parent){ //未回溯到根结点
if(qp->lchild == q)return qp;//找到1)b)所述结点
q = qp;//往上回溯 }
return NULL;//未找到 }
1 数据结构试卷（二） 一、选择题(24分) 1．下面关于线性表的叙述错误的是（）。(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空......
数据结构试卷（十）一、选择题(24分) 1．下列程序段的时间复杂度为（）。i=0，s=0； while(s）存储方式最节省运算时间。(A) 单向链表(B) 单向循环链表 (C) 双向链表(D) 双向循环链表3．设指针......
全国2012年10月高等教育自学考试数据结构导论试题及答案课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1.答题前，考生务必将自己的考......
刀豆文库小编为你整合推荐5篇数据结构试题，也许这些就是您需要的文章，但愿刀豆文库能带给您一些学习、工作上的帮助。......
数据结构试题一、选择题(30分)1.下列程序段的时间复杂度为( )。(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2.设顺序线性表中有n个数据元素，则删除表中第i个元素需......
