数据结构试题及答案.docx
- 文档编号:16706154
- 上传时间:2023-07-16
- 格式:DOCX
- 页数:103
- 大小:216.91KB
数据结构试题及答案.docx
《数据结构试题及答案.docx》由会员分享,可在线阅读,更多相关《数据结构试题及答案.docx(103页珍藏版)》请在冰点文库上搜索。
数据结构试题及答案
单选题(每题2分,共20分)
1.1.对一个算法的评价,不包括如下(B)方面的内容。
A.健壮性和可读性B.并行性C.正确性D.时空复杂度
2.2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行(A)o
A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;
C.p->next=HL;p=HL;D.HL=p;p->next=HL;
3.3.对线性表,在下列哪种情况下应当采用链表表示?
(B)
A.经常需要随机地存取元素B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变
4.4.一个栈的输入序列为123,则下列序列中不可能是栈的输出序列的是
(C)
A.231
C.312
B.321
D.123
5.5.AOV网是-
种(D)o
A.有向图
B.无向图
C.无向无环图
D.有向无环图
6.6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)o
A.低于链接法处理冲突B.高于链接法处理冲突
C.与链接法处理冲突相同D.高于二分查找
7.7.若需要利用形参直接访问实参时,应将形参变量说明为(D)参数。
A.值B.函数C.指针D.引用
8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的(A)o
A.行号B.列号C.元素值D.非零元素个数
9.9.快速排序在最坏情况下的时间复杂度为(D)o
A.O(log2n)B.0(nlog2n)C.0(n)D.0(n2)
10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为(C)o
A.O(n)B.O
(1)C.O(log2n)D.O(n2)
二、运算题(每题6分,共24分)
1.1.数据结构是指数据及其相互之间的当结点之间存在M
对N(M:
N)的联系时,称这种结构为o
2.2.队列的插入操作是在队列的__尾行,删除操作是在队列的—
首行。
3.3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则
表示栈满的条件是top==0(要超出才为满)o
4.4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度
为在表尾插入元素的时间复杂度为o
5.5.设W为一个二维数组,其每个数据元素占用4个字节,行下标i从0
到7,列下标j从0到3,贝「维数组W的数据元素共占用个字
节。
W中第6行的元素和第4列的元素共占用个字节。
若按行
顺序存放二维数组W,其起始地址为100,则二维数组元素W[6,3]的起始地址为。
6.6.广义表A=(a,(a,b),((a,b),c)),则它的深度为它的长度为
7.7.二叉树是指度为2的寸。
一棵结点数为N的二叉
树,其所有结点的度的总和是。
8.8.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个
。
对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的。
9.9.对于一棵具有n个结点的二叉树,用二叉链表存储时,其指针总数为
个,其中个用于指向孩子,
指针是空闲的。
10.10.若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存
储到一维数组A中,即编号为0的结点存储到A[0]中。
其余类推,贝UA[i]元素的左孩子元素为,右孩子元素为,双亲元素为
11.11.在线性表的散列存储中,处理冲突的常用方法有
和种。
12.12.当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用
卡序;当待排序的记录数较大,存储空间允许且要求排序是稳定时,宜米用卡序。
运算题
(每题6分,共24分)
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
5
0
0
0
0
0
0
7
0
0
1.
试:
已知一个
6
5稀疏矩阵如下所示,
(1)写出它的三元组线性表;
(2)给出三元组线性表的顺序存储表示。
2.设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起,逐个输入各个数据而生成的二叉搜索树。
3.对于图6所示的有向图若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,试写出:
(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树;
(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树;
4.已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={<2,1>,v3,2>,v3,6>,v4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>}
若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,按主教材中介绍的拓朴排序算法进行排序,试给出得到的拓朴排序的序列。
四、阅读算法(每题7分,共14分)
1.1.intPrime(intn)
{
inti=1;
intx=(int)sqrt(n);
while(++i<=x)
if(n%i==0)break;
if(i>x)return1;
elsereturn0;
}
(1)指出该算法的功能;
(2)该算法的时间复杂度是多少?
2.写出下述算法的功能:
voidAJ(adjlistGL,inti,intn)
{
QueueQ;
InitQueue(Q);coutvvivv'';visited[i]=true;
Qinsert(Q,i);
while(!
QueueEmpty(Q)){
intk=QDelete(Q);
edgenode*p=GL[k];
while(p!
=NULL){
intj=p->adjvex;
if(!
visited[j])
{
coutvvjvv'';
visited[j]=true;
Qinsert(Q,j);
}
p=p->next;
}}
}
五、算法填空(共8分)
如下为二分查找的非递归算法,试将其填写完整。
intBinsch(ElemTypeA[],intn,KeyTypeK)
{
intlow=0;
inthigh=n-1;
while(low<=high)
{
intmid=;
if(K==A[mid].key)returnmid;〃查找成功,返回元素的下标
elseif(K<[mid].key)
;//在左子表上继续查找
else;//在右子表
上继续查找
}
return-1;〃查找失败,返回-1
}
六、编写算法(共8分)
HL是单链表的头指针,试写出删除头结点的算法。
ElemTypeDeleFront(LNode*&HL)
1.B
24
3.B
4.C
2.
3.
4.
四、
1.
2.
五、
六、
1.
2.
3.
4.
5.
6.
联系
尾
top==0
0
(1)
12844
33
单选题
5.D6.B
填空题
(或图结构)
O(n)
108
(每题
7.D
(每空
参考答案
2分,共20分)
8.A9.D10.C
1分,共26分)
6
5
5
1
5
1
3
2
-1
4
5
-2
5
1
5
6
3
7
图7
如图8所示。
DFS:
BFS:
拓朴排序为:
7.
有序
n-1
8.
有序序列
后缀表达式(或逆波二式)
9.
2nn-1
n+1
10.
2i+1
2i+2(i-1)/2
11.
开放定址法
链接法
12.
快速
归并
三、
运算题(每题6分,共24分)
1.
(1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))
三兀组线性表的顺序存储表示如图
7示。
(3分)
■J
餡(21
365
(每题7分,共14分)
阅读算法
判断n是否是素数(或质数)
0(■n)
(2)
功能为:
从初始点vi出发广度优先搜索由邻接表算法填空(8分)
(low+high)/2high=mid-1
编写算法(8分)
ElemTypeDeleFront(LNode*&HL){
if(HL==NULL){
cerr<<"空表"< (1); } LNode*p=HL; HL=HL->next; ElemTypetemp=p->data;deletep; returntemp; GL所表示的图。 low=mid+1 单选题(每题2分,共20分) 1.栈和队列的共同特点是(A)。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列,在进行插入运算时(D). A.仅修改头指针B.头、尾指针都要修改 C.仅修改尾指针D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构? (D) A.队列B.栈C.线性表D.二叉树 4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置? 脚注(10)表示用10进制表示。 B.678 C.692D.696 5.树最适合用来表示()。 B.无序数据元素 D.元素之间无联系的数据 D.2k-1 A.有序数据元素 C.元素之间具有分支层次关系的数据 6.二叉树的第k层的结点数最多为(). A.2k-1B.2K+1C.2K-1 7.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为() B. A.1,2,3 9,5,2,3 C.9,5,3D.9,4,2,3 8.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为 A.O (1)B.O(n)C.O(1og2n)D.O(n2) 9.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选 用H(K)=K%9作为散列函数,则散列地址为1的元素有()个, A.1B.2C.3D.4 10.设有6个结点的无向图,该图至少应有()条边才能确保是一个连通 图。 A.5B.6C.7D.8 填空题(每空1分,共26分) 1.通常从四个方面评价算法的质量: O 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为 3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所 含的结点数为,树的深度为树的度为。 4.后缀算式923+-102/-的值为中缀算式(3+4X)-2Y/3对应 的后缀算式为 5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩 子的两个指针。 在这种存储结构中,n个结点的二叉树共有指针域, 其中有指针域是存放了地址,有指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中, 所含边结点分别有和。 7.AOV网是一种■勺图。 8.在一个具有n个顶点的无向完全图中,包含有边,在一个具有n 个顶点的有向完全图中,包含有边。 9.假定一个线性表为(12,23,74,55,63,40,若按Key%4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为 和。 10.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,贝慚树比原 树的高度。 11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为, 整个堆排序过程的时间复杂度为。 12.在快速排序、堆排序、归并排序中,卡序是稳定的。 三、运算题(每题6分,共24分) 1. datanext 在如下数组A中链接存储了一个线性表,表头指针为A[0].next,试写出该线性表。 A0123456 60 50 78 90 34 40 3 5 7 2 0 4 1 2.请画出图10的邻接矩阵和邻接表。 3.已知一个图的顶点集V和边集E分别为: V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边。 4.画出向小根堆中加入数据4,2,5,8,3时,每加入一个数据后堆的变化 四、阅读算法(每题7分,共14分) 1.LinkListmynote(LinkListL) {//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L;L=L—>next;p=L; S1: while(p—>next)p=p—>next; S2: p—>next=q;q—>next=NULL; }returnL; } 请回答下列问题: (1)说明语句S1的功能; (2)说明语句组S2的功能; (3)设链表表示的线性表为(a1,a2,…耳),写出算法执行后的返回值所表示的线性表。 2.voidABC(BTNode*BT) { ifBT{ ABC(BT->left); ABC(BT->right); cout< } } 该算法的功能是: 五、算法填空(共8分) 二叉搜索树的查找一一递归算法: boolFind(BTreeNode*BST,ElemType&item) { if(BST==NULL) returnfalse;//查找失败 else{ if(item==BST->data){ item=BST->data;//查找成功 return;} elseif(item returnFind,item); elsereturnFind,item); }//if 六、编写算法(共8分) 统计出单链表HL中结点的值等于给定值X的结点数 intCountX(LNode*HL,ElemTypex) 参考答案 一、单选题(每题2分,共20分) 1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A 二、填空题(每空1分,共26分) 1.正确性易读性强壮性高效率 2.0(n) 3.933 4.-134X*+2Y*3/- 5.2nn-1n+1 6.e2e 7.有向无回路 8.n(n-1)/2n(n-1) 9.(12,40)()(74)(23,55,63) 10.增加1 11.O(log2n)O(nlog2in) 12.归并 运算题(每题6分,共24分) 1.线性表为: (78, 50: ,40, 60,34,90) 0 1 11 0 1 0 10 1 1 1 01 1 1 0 10 1 2.邻接矩阵: 0 1 11 0 邻接表如图 11所示: 图11 3.用克鲁斯卡尔算法得到的最小生成树为: (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.见图12 图12 四、阅读算法(每题7分,共14分) 1. (1)查询链表的尾结点 (2)将第一个结点链接到链表的尾部,作为新的尾结点 (3)返回的线性表为(a2,a3,…,an,a1) 2.递归地后序遍历链式存储的二叉树。 五、算法填空(每空2分,共8分) true 六、 BST->leftBST->right 编写算法(8分) intCountX(LNode*HL,ElemTypex) {inti=0;LNode*p=HL;//i为计数器while(p! =NULL) {if(P->data==x)i++;p=p->next; }//while,出循环时i中的值即为x结点个数 returni; }//CountX 单选题(每小题2分,共8分) 1、在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时的平均查找长度(即x与元素的平均比较次数,假定查找每个元素的概率都相等)为()。 AnBn/2C(n+1)/2D(n-1)/2 2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。 As—link=pflink;p—link=s;Bp—link=s;s—link=q; Cp—link=s—link;s—link=p;Dq—link=s;s—link=p; 3、栈的插入和删除操作在()进行。 A栈顶 B栈底 C任意位置 D 指定位置 4、由权值分别为 11,8,6, 2,5的叶子结点生成一棵哈夫曼树,它的带权路 径长度为() A24 B71 C48 D 53 填空题(每空1分,共32分) 1、数据的逻辑结构被分为、、和 四种。 2、一种抽象数据类型包括和个部分。 3、在下面的数组a中链接存储着一个线性表,表头指针为a[o].next,则该线性表为。 60 56 42 38 74 25 4 3 7 6 2 0 1 a0123 45678 datanext 4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,判断链 表为空的条件分别为和。 5、用具有n个元素的一维数组存储一个循环队列,则其队首指针总是指向 队首元素的,该循环队列的最大长度为。 6、当堆栈采用顺序存储结构时,栈顶元素的值可用表示; 当堆栈采用链接存储结构时,栈顶元素的值可用示。 7、一棵高度为5的二叉树中最少含有结点,最多含有 个结点; 一棵高度为5的理想平衡树中,最少含有结点,最多含有 结点。 &在图的邻接表中,每个结点被称为,通常它包含三个域: _k日一日一日 疋;二二二是三疋。 9、在一个索引文件的索引表中,每个索引项包含对应记录的和 项数据。 10、假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J))), 则树中所含的结点数为个,树的深度为树的度为 结点H的双亲结点为孩子结点为。 11、在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为 整个堆排序过程的时间复杂度为。 12、在对m阶的B_树插入元素的过程中,每向一个结点插入一个索引 项(叶子结点中的索引项为关键字和空指针)后,若该结点的索引项数等于,则必须把它分裂为结点。 运算题(每小题6分,共24分) 1、已知一组记录的排序码为(46,79,56,38,40,80,95,24),写出对其进行快速排序的每一次划分结果。 2、一个线性表为B=(12,23,45,57,20,03,78,31,15,36),设散列表为HT[0..12],散列函数为H(key)=key%13并用线性探查法解决冲突,请画出散列表,并计算等概率情况下查找成功的平均查找长度。 3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结 果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。 4、已知一个图的顶点集V各边集G如下: V={0,1,2,3,4,5,6,7,8,9}; E={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,9),(6,7),(7,8),(8,9)} 当它用邻接矩阵表示和邻接表表示时,分别写出从顶点V0出发按深度优先 搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。 假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 图 深度优先序列 广度优先序列 邻接矩阵表示时 邻接表表示时 34-1,请 1假定从键盘上输入一批整数,依次为: 7863453091写出输出结果。 #inelude #inelude consstintstaekmaxsize=30; typedefintelemtype; structstack{ elemtypestack[stackmaxsize]; inttop; }; #include“stack.h” Voidmain() { stacka; initstack(a); intx; cin>>x; while(x! =-1){ push(a,x);cin>>x; } while(! stackempty(a)) cout< cout< } 该算法的输出结果为: 2、阅读以下二叉树操作算法,指出该算法的功能。 Template : unknown(BinTreeNode BinTreeNode if(p! =NULL){ temp=p—leftchild; pfleftchild=prightchild; pfrightchild=temp;unknown(pfleftchild);undnown(pfrightchild); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试题 答案
![提示](https://static.bingdoc.com/images/bang_tan.gif)