数据结构考试题⽬
数据结构49道题
1. 数据结构是⼀门研究什么内容的学科？
c语言基本名词概念2. 数据元素之间的关系在计算机中有⼏种表⽰⽅法？各有什么特点？
3. 数据类型和抽象数据类型是如何定义的。⼆者有何相同和不同之处，抽象数据类型的主要特点是什么？
使⽤抽象数据类型的主要好处是什么？
5．评价⼀个好的算法，您是从哪⼏⽅⾯来考虑的？
8．对于⼀个数据结构，⼀般包括哪三个⽅⾯的讨论？
9. 当你为解决某⼀问题⽽选择数据结构时，应从哪些⽅⾯考虑？
11．数据结构与数据类型有什么区别？
15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?
18．设计⼀数据结构，⽤来表⽰某⼀银⾏储户的基本信息：账号、姓名、开户年⽉⽇、储蓄类型、存⼊
累加数、利息、帐⾯总数。
19. 请在下列算法的横线上填⼊适当的语句。
FUNCTION inclusion(ha,hb:linklisttp):boolean;
{以ha 和hb 为头指针的单链表分别表⽰有序表A 和B，本算法判别表A 是否包含在表B 内，若是，则
返回“true”，否则返回“false”}
BEGIN
pa:=ha^.next; pb:=hb^.next; （1） ;
WHILE（2） DO
IF pa^.data=pb^.data THEN（3） ELSE（4） ;
（5）
END;
20．完善算法：已知单链表结点类型为：
TYPE ptr=^node；
node=RECORD
data：integer； next：ptr
END；
过程create 建⽴以head 为头指针的单链表。
PROCEDURE create ( (1) )；
VAR p,q：ptr； k：integer；
BEGIN
new（head）； q:=head；read（k）；
WHILE k>0 DO
BEGIN
(2); (3); (4); (5);
read（k）
END;
q^.next：=NIL;
END;
22．假设链表p 和链表q 中的结点值都是整数，且按结点值的递增次序链接起来的带表头结点的环形链表。各链表的表头结点的值为max，且链表中其他结点的值都⼩于max，在程序中
取max 为9999。在各个链表中，每个结点的值各不相同，但链表p 和链表q 可能有值相同的结点（表头结点除外）。下⾯的程序将链表q合并到链表p 中，使得合并后的链表是按结点值递增次序链接起来的带表头结点的环形链表，且链表中各个结点的值各不相同。请在划线处填上适当内容，每个框只填⼀个语句或⼀个表达式，链表的结点类型如下
TYPE nodeptr=^nodetype；
nodetype=RECORD
data：integer； link：nodeptr;
END；
CONST max=9999;
PROCEDURE merge(VAR p:nodeptr;q:nodeptr);
VAR r,s: nodeptr;
BEGIN
r:=p;
WHILE (A)___ DO
BEGIN
WHILE r^.link^.data
IF r^.link^.data>q^.link^.data
THEN BEGIN s:=(C)_; (D)_:=s^.link; s^.link:=(E)_; (F)_ _:=s; (G)_; END
ELSE BEGIN (H)__; s:=q^.link; (I)__; dispose(s) END
END;
dispose(q)
END;
24. 已知双链表中结点的类型定义为：
TYPE dpointer=^list;
list=RECORD
data:integer; left,right:dpointer;
END;
如下过程将在双链表第i 个结点（i>=0）之后插⼊⼀个元素为x 的结点，请在答案栏给出题⽬中______处
应填⼊的语句或表达式，使之可以实现上述功能。
PROCEDURE insert(VAR head:dpointer;i,x:integer);
VAR s,p:dpointer; j: integer;
BEGIN
new(s); s^.data:=x;
IF(i=0)THEN BEGIN s^.right:=head; (1)___ head:=s END{如果i=0，则将s 结点插⼊到表头后返回}
ELSE BEGIN p:=head; (2)_______；{在双链表中查第i 个结点，由p 所指向}
WHILE ((p<>NIL) AND (j
IF p<>NIL THEN
IF （p^.right=NIL）
THEN BEGIN p^.right:=s; s^.right:=NIL; (4) __END
ELSE BEGIN s^.right:=p^.right; (5) _;p^.right:=s; (6) END
ELSE writeln(‘can not find node!’)
END
END;
27．对于给定的线性链表head , 下⾯的程序过程实现了按结点值⾮降次序输出链表中的所有结点，在每次输出⼀个结点时，就把刚输出的结点从链表中删去。请在划线处填上适当的内容，使之成为⼀个完整的程序过程，每个空框只填⼀个语句。
TYPE nodeptr =^ nodetype；
nodetype = RECORD
data : integer；link : nodeptr
END;
VAR head : nodeptr；
PROCEDURE sort_output_delete (head : nodeptr);
VAR p,q,r,s: nodeptr;
BEGIN WHILE head <> NIL DO
BEGIN p:= NIL ；q:= head；r:= q ；s:=q^.link ；
WHILE s <> NIL DO
BEGIN IF s^.data < q^.data THEN BEGIN (1)__; (2)___ END ；
r:= s ； (3)___
END；
write(q^.data : 5) ；
IF p=NIL THEN (4)___ ELSE (5)____ ；
dispose (q) ；
END；
writeln
END；
2．线性表的顺序存储结构具有三个弱点：其⼀，在作插⼊或删除操作时，需移动⼤量元素；其⼆，由于难以估计，必须预先分配较⼤的空间，往往使存储空间不能得到充分利⽤；其三，表的容量难以扩充。线性表的链式存储结构是否⼀定都能够克服上述三个弱点，试讨论之。
7. 试述头结点,⾸元结点，头指针这三个概念的区别.
14. 有线性表(a1,a2,…,a n)，采⽤单链表存储，头指针为H，每个结点中存放线性表中⼀个元素，现查某个元素值等于X 的结点。分别写出下⾯三种情况的查语句。要求时间尽量少。（1）线性表中元素⽆序。（2）线性表中元素按递增有序。（3）线性表中元素按递减有序。19．设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre 和next，试写出在指针p 所指结点之前插⼊⼀s 结点的C 语⾔描述语句。
1. 名词解释：栈。
2. 名词解释：队列
3. 什么是循环队列？
14. 当过程P 递归调⽤⾃⾝时，过程P 内部定义的局部变量在P 的2 次调⽤期间是否占⽤同⼀数据区？为什么？
32. 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队⾸指针与队尾指针的值。
35. 如果⽤⼀个循环数组-1]表⽰队列时，该队列只有⼀个队列头指针front，不设队列尾指针rear，⽽改置计数器count ⽤以记录队列中结点的个数。
（1）编写实现队列的三个基本运算：判空、⼊队、出队（3 分）
（2）队列中能容纳元素的最多个数是多少？（1 分）
15. 所谓稀疏矩阵指的是_______。
16. 对矩阵压缩是为了_______。
6. 三维数组A[1..10,-2..6,2..8]的每个元素的长度为4 个字节，试问该数组要占多少个字节的存储空间？如果数组元素以⾏优先的顺序存贮，设第⼀个元素的⾸地址是100，试求元素A[5,0,7] 的存贮⾸地址。
37.⽤三元数组表⽰稀疏矩阵的转置矩阵，并简要写出解题步骤。（10 分）
1．从概念上讲，树，森林和⼆叉树是三种不同的数据结构，将树，森林转化为⼆叉树的基本⽬的是什么，并指出树和⼆叉树的主要区别。
53. 已知⼀个森林的先序序列和后序序列如下，请构造出该森林。
先序序列：ABCDEFGHIJKLMNO
后序序列：CDEBFHIJGAMLONK
64．设⼆叉树的存储结构如下(每题5 分，共15 分)
LINK 0 0 2 3 7 5 8 0 10 1
INFO J H F D B A C E G I
RLINK 0 0 0 9 4 0 0 0 0 0
其中,T 为树根结点的指针,LLINK、RLINK 分别指向结点的左右⼦⼥,INFO 为其数据域，请完成下列各题:
（1）画出⼆叉树T 的逻辑结构. （2）写出按前序、中序和后序周游⼆叉树T 得到的结点序列.
（3）画出⼆叉树T 的后序线索树。
67．按下⾯要求解下图中⼆叉树的有关问题：
(1)对此⼆叉树进⾏后序后继线索化；(2)将此⼆叉树变换为森林；
(3)⽤后根序遍历该森林，；写出遍历后的结点序列。
6．⽤邻接矩阵表⽰图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？7．请回答下列
关于图(Graph)的⼀些问题：（每题4 分）（1）．有n 个顶点的有向强连通图最多有多少条边?最少有多少条边?
（2）．表⽰有1000 个顶点、l000 条边的有向图的邻接矩阵有多少个矩阵元素？是否稀疏矩阵？
（3）．对于⼀个有向图，不⽤拓扑排序，如何判断图中是否存在环？
9．有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）．写出顶点a 到顶点i 的全部简单路径。13．假定Ｇ＝（V，E）是有向图，V＝｛1,2，．．．,N｝，N＞＝1，G 以邻接矩阵⽅式存储，G 的邻接矩阵为A，即Ａ是⼀个⼆维数组，如果i 到j 有
边，则A[i,j]=1，否则A[i,j]=0，请给出⼀个算法，该算法能判断G是否是⾮循环图（即G 中是否存在回路），要求算法的时间复杂性为O(n*n)。14．⾸先将如下图所⽰的⽆向图给出其存储结构的邻接链表表⽰，然后写出对其分别进⾏深度，⼴度优先遍历的结果。
17．设G=(V,E)以邻接表存储，如图所⽰，试画出图的深度优先和⼴度优先⽣成树。
27．已知⼀个⽆向图如下图所⽰，要求分别⽤Prim 和Kruskal 算法⽣成最⼩树（假设以①为起点，试画
出构造过程）。
33．已知世界六⼤城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L) 、东京(T) 、墨西哥(M)，下表给定了这六⼤城市之间的交通⾥程：
42．试利⽤Dijkstra 算法求下图中从顶点a 到其他个顶点间的最短路径，写出执⾏算法过程中各步的状
态

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。