计算机专业数据结构模拟试题
一、判断题 (每小题1分，共15分)
1.非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( )
2.数组是一种没有插入与删除*作的线性结构。( )
3.稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。( )
4.空串与由空格组成的串没有区别。( )
5.将T在S中首次出现的位置作为T在S中的位置的*作称为串的模式匹配。( )
6.深度为h的非空二叉树的第i层最多有2h-1 个结点。( )
7.完全二叉树就是满二叉树。( )
8.已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( )
9.非空二叉排序树的任意一棵子树也是二叉排序树。( )
10.有向图是一种非线性结构。( )
11.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )
12.AOE 网是一种带权的无环连通图。( )
13.折半查找方法适用于按值有序的线性链表的查找。( )
14.哈希表的查找效率主要取决于所选择的哈希函数与处理冲突的方法。( )
15.选择排序过程中元素之间的比较次数与原始序列的状态无关。( )
二、单项选择题 (每小题2分，共20分)
1.若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动
_______个数据元素。( )
A.n-i
B.n+i
C.n-i-1
D.n-i+1
2.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q 和p指的结点之间插入一
个由s指的结点，则需执行________。( )
A.link(s)←link(p)，lin k(p)←s
B.link(q)←s，link(s)←p
C.link(p)←link(s)，link(s)←p
D.link(p)←s，link(s)←q
3.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语
句依次为:rlink(p)←q,llink(p)←llink(q),llink←p,_________。（空白处为一条赋值语句
）( )
A.rlink(q)←p
B.rlink(llink(q)←p
C.rlin k(llink(p))←p
D.rlink(rlink(p)←p
4.为了节省存储空间，将n阶对称矩阵A中包括主对角线元素在内的下三角部分的所有元素按
照行序为主序方式存放在一维数组B[1:n(n-1)/2]中，对任意下三角部分的元素aij(i≥j)在B
的下标k是 ( )
A.i(i-1)/2+j
B.(i(i-1))/2+j
B.(i(i+1))/2+j
5.某堆栈的输入序列为a,b,c,d,下面的四个序列中，__________不可能是它的输出序列。(
)
A.a,c,b,d
B.b,c,d,a
C.d,c,a,b
D.c,d,b,a
6.若非空队列采用链式存储结构，front和rear分别为队头元素与队列尾元素的指针，删除
此时队列的一个元素的*作时依次执行p←front，_________________ ，call RET(P)。( )
A.front←link(rear)
B.rear←link(p)
C.rear←link(front)
D.f ront←link(p)
7.中缀表达式A-(B+C)*D/E的后缀形式是_________________。( )
A.ABC+-D*E/
B.ABC+D*-E/
D.ABC+D*E/-
8.广大义表A=((),(a),(b,(c,d)))的长度为 ( )
A.2
B.3
C.4
D.5
9.在初始为空的杂凑表中依次插入关键字序列(MON，TUE，WED，THU，FRI，SAT，SUN), 杂
凑函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为
[0:6]，采用线性再散列法处理冲突。插入后的杂凑表应该如
________________所示。( )
A. 0 1 2 3 4 5 6
THU TUE WED FRI SUN SAT MON
B. 0 1 2 3 4 5 6
TUE THU WED FRI SUN SAT MON
C. 0 1 2 3 4 5 6
TUE THU WED FRI SAT SUN MON
D. 0 1 2 3 4 5 6
TUE THU WED SUN SAT FRI MON
10.从未排序序列中选择一个元素，该元素将未排序序列分成前后两个部分，前一部分中所
有元素都小于等于所选元素。后一部分中所有元素都大于等于所选元素，而所选元素处在排序
的最终位置。这种排序方法称为_____________排序法。( )
A.插入
B.谢尔
C.快速
D.堆积
三、填空题 (每小题2分，共20分)
1.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的
地址为LOC(a1)，那么，LOC(ai)=___________________。
2.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为______________。
3.具有n个结点的非空二叉排序树的最小深度为
___________________。
4.深度为h且有_______________个结点的二叉树称为满二叉树。(设根结点处在第1层)。
5.二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G?
珼，H，其后序遍历序列为__________________。
6.已知序列(34，76，45，18，26，54，92，65，)，按照逐点插入法建立一棵二叉排序列树
，该树的深度是__________________。
7.一个不带有权的有向图采用邻接矩阵存储方法，其邻接矩阵是一个__________________。
8.带权连通图G=
V={v1,v2,v3,v4,v5,},E={(v1,,v2)7,(v1,v4)6，(v1,v4)9，
(v2,v3)8，(v2,v4)4，(v2,v5)4，(v3,v4)6，(v4,v5)2，(注：顶点偶对右下角的数据为边上的
权值)，G的最小生成树的权值之和为__________________ 。
9.在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表中元素应该按值有
序，并且采用______________存储方法。
10.若对序列(49，38，65，97，76，13，27，50)采用选择排序法排序，则第三趟结束后序
列的状态是___________________。
四、问题求解题 (每小题10分，共20分)
1.已知AOE网为G=(V,E)，其中,
V ={v1,v2,v3,v4,v5,v6,v7},
E = {a1,a2,a3,a4,a5,a6,a7,a8,a9,a10},
a1:(v1,v2)3,a2:(v1,v3)2,a3:(v2,v4)1,a4:(v2,v5)8,a5:(v3,v4) 3,
a6:(v3,v6)7,a7:(v4,v5)4,a8:(v4,v6)2,a9:(v5,v7)9,a10:(v6,v7 )6；
(注：顶点偶对的右括号下方的数据表示该边上的权值)。e与l分别表示活动a1的最
早开始时间与最晚开始时间，请分别求出e与l(1≤i≤10),填入下面的方格中。
e[1:10]
l[1:10]
2.若对序列(76，38，65，13，97，27，50，49)采用堆积排序法(按照值的大小从小到大)进
行排序，请分别在下表中写出每一趟的结果：
原始序列 76 38 65 13 97 27 50 49
第1趟结果
第2趟结果
第3趟结果
第4趟结果
第5趟结果
第6趟结果
第7趟结果
第8趟结果
五、算法题 (共25分)
1.已知长度为n的线性表A采用顺序存储结构，并且元素按值大小非递减排列，下面的算法删
除线性表中多余的值相同的元素。请在算法的空白处填入适当内容，使之能够正常工作。(10
分)
procedure DEL (A,n)
i←1
while ____________ do
if (A≠A[i+1] then
i←i+1
else // 查找满足条件的元素 // [ for _________ do
A[j-1]←A[j]
end // 删除第i+1个元素 (满足条件的元素) //
______________ ] // 修改线性表的长度 //
end
end
2.已知非空线性链表的链结点的构造为 date | link，第一个链结点的指针为list，下面的
算法删除链表的第i个结点（设i>0）。请在算法的空白处填入适当内容，使之能够正常工作。
(15分)
procedure DEL (list,i,item)
_____________ // 给变量q赋初值 //
if (i=1) then
list←link(q) // 删除第一个链结点 //
else
[ for j←1 to ______________ do
r←q
q←link (q)
if _________ then
[ call ERROR (i 超过链表的长度！’) return ]
end // r与q分别指向第i-1个与第i个链结点 //
_____________ ]
// 删除第i个链结点 // call RET(q) // 删除被删除链结点的空间//
2010-2011 学年第2 学期课号BT11107 课程名称数据结构（B卷; 闭卷）适用班级（或年级、专业）08011103、104、105 一、填空题（每小题2分，共20分） (1) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的 （）和运算等的学科。 (2)在一个长度为n的顺序表中第i个元素（1 ≤i ≤n）之前插入一个元素时，需向后 移动（）个元素。 (3）假设以S和X分别表示进栈和退栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为（）。 （4）数据的逻辑结构在计算机存储器内的表示，称为数据的（）。 （5）在具有n个单元的循环队列中，队满时共有____个元素。 （6）二叉树有（）种基本形态。 （7）在具有n个结点的完全二叉树中，若结点i有左孩子，则结点i的左孩子编号为（）。（8）若用二叉树表示具有n个结点的二叉树，则有（）个空链域。 （9）深度为k（k>0）的二叉树，至多有（）个结点，第i层上之多有（）结点。 (10) 一个有n个顶点的无向图最多有____条边。 二、选择题（每小题2分，共20分） 1.研究数据结构就是研究（）。 (A) 数据的逻辑结构 (B) 数据的存储结构 (C) 数据的逻辑结构和存储结构 (D) 数据的逻辑结构、存储结构及其数据的运算 2.下列算法的时间复杂度是（） s=0; for (i=0;i 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 计算机专业基础综合（数据结构）模拟试卷1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。 （分数：2.00） A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表√ 解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。 3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。 （分数：2.00） A.O(l) B.O(ls) C.O(min(l，s)) D.O(max(l，s)) √ 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。 4.线性表中存放的主要是( )。 （分数：2.00） A.整型常量 B.字符 C.数据元素√ D.信息元素 解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。 5.下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比 （分数：2.00） A.仅I √ B.仅Ⅱ C.仅Ⅲ D.I、Ⅱ、Ⅲ 解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。 6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。 （分数：2.00） A.顺序表√ 第六章树 1. 对于图6.29给出的树，指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。 2. 对图6.29所示的树，采用先根次序、后根次序和中根次序遍历。问得到怎样的结点序列？ 3. 对图6.29所示的树，分别采用先根次序的父指针表示法、长子-兄弟表示法，试画出各种方法的图示。 4. 用三个结点A，B，C可以构成多少种不同的二叉树？请把它们画出来。 5. 将图 6.29所示的树转换成对应的二叉树是什么样子？请把它画出来。 6. 请按先根、后根和对称序遍历图6.30所示的二叉树，列出遍历所得的结点序列。 7 请将图6.30所示的二叉树转换成对应的树林，并按先根次序和后根次序遍历树林。 8. 对于给定的一组权值 w＝｛1，4，9，16，25，36，49，64，81，100｝， 构造具有Huffman树。并求出它的带权路径长度。 9 给出(a)所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？ 10．画出下图所示的各二叉树所对应的森林。 11．假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。 1) 为这8个字母设计Huffman编码。 26构造连通网最小生成树的两个典型算法是______。 27．求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。 28. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 2018计算机考研：计算机数据结构测试题(四) 2018考研，计算机专业课考试科目为：计算机组成原理、数据结构、操作系统以及计算机网络等，需要大家记忆的知识点有很多，但是不能死机硬背，还是要理解为主的，融会贯通才能把题做好，拿到高分，小编就为大家分享计算机数据结构测试题及参考答案，希望计算机考研的考生在复习之余能够认真做题，巩固知识。 计算机数据结构测试题(四) 一、选择题(30分) 1.设某无向图有n个顶点，则该无向图的邻接表中有( )个表头结点。 (A) 2n (B) n (C) n/2 (D) n(n-1) 2.设无向图G中有n个顶点，则该无向图的最小生成树上有( )条边。 (A) n (B) n-1 (C) 2n (D) 2n-1 3.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。 (A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80 (C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80 4.( )二叉排序树可以得到一个从小到大的有序序列。 (A) 先序遍历(B) 中序遍历(C) 后序遍历(D) 层次遍历 5.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为( )。 (A) 2i+1 (B) 2i (C) i/2 (D) 2i-1 6.程序段s=i=0;do {i=i+1; s=s+i;}while(i<=n);的时间复杂度为( )。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2) 7.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。 (A) head==0 (B) head->next==0 (C) head->next==head (D) head!=0 8.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有( )。 (A) 20 (B) 256 (C) 512 (D) 1024 9.设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为( )。 (A) 1 (B) 2 (C) 3 (D) 4 10.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( )。 (A) top=top+1; (B) top=top-1; (C) top->next=top; (D) top=top->next; 二、判断题(20分) 1.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。( ) 2.当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。( ) 3.设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。( ) 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) [考研类试卷]计算机专业基础综合数据结构（概论）历年真题试卷汇编 2 一、单项选择题 1 以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】 （A）栈 （B）广义表 （C）有向图 （D）字符串 2 以下数据结构中，( )是非线性数据结构【中山大学1999一、4】 （A）树 （B）字符串 （C）队 （D）栈 3 下列数据中，( )是非线性数据结构。【北京理工大学2001六、1(2分)】（A）栈 （B）队列 （C）完全二叉树 （D）堆 4 连续存储设计时，存储单元的地址( )。【中山大学1999一、1(1分)】 （A）一定连续 （B）一定不连续 （C）不一定连续 （D）部分连续，部分不连续 5 以下属于逻辑结构的是( )。【西安电子科技大学应用2001一、1】 （A）顺序表 （B）哈希表 （C）有序表 （D）单链表 6 算法的计算量的大小称为计算的( )。【北京邮电大学2000二、3(20／8分)】（A）效率 （B）复杂性 （C）现实性 （D）难度 7 算法的时间复杂度取决于( )。【中科院计算所1998二、1(2分)】 （A）问题的规模 （B）待处理数据的初态 （C）A和B 7 计算机算法指的是(1)，它必须具备(2)这三个特陛。【南京理工大学1999一、 1(2分)】 8 (1) （A）计算方法 （B）排序方法 （C）解决问题的步骤序列 （D）调度方法 9 (2) （A）可执行性、可移植性、可扩充性 （B）可执行性、确定性、有穷性 （C）确定性、有穷性、稳定性 （D）易读性、稳定性、安全性 10 一个算法应该是( )。【中山大学1998二、1(2分)】 （A）程序 （B）问题求解步骤的描述 （C）要满足五个基本特性 （D）A和C 11 下面说法错误的是( )。【南京理工大学2000一、2(1．5分)】 (1)算法原地工作的含义是指不需要任何额外的辅助空间 (2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(22)的算法 (3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 (4)同一个算法，实现语言的级别越高，执行效率就越低 少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 1、设有如下遗产继承规则：丈夫和妻子可以互相继承遗产，子女可以继承父亲或母亲的遗产，子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（）。 A. 树 B. 图 C. 数组 D. 二叉树 2、下列排序中，占用辅助空间最多的是（）。 A. 堆排序 B. 冒泡排序 C. 直接选择排序 D. 二路归并 3、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。 A. 选择排序 B. 冒泡排序 C. 希尔排序 D. 插入排序 4、在待排序序列局部有序的情况下，最好的内部排序应该是（）。 A. 直接选择排序 B. 堆排序 C. 直接插入排序 D. 快速排序 5、下列排序算法中不稳定的是（）。 A. 直接选择排序 B. 直接插入排序 C. 起泡排序 D. 归并排序 6、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4 一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。 计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x； （分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)； （分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 （分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++； （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】 （分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点 解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】 （分数：2.00） A.数据项 B.数据类型 C.数据元素√ 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 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. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后 课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。 《数据结构》模拟题（开卷） 一、单项选择题 1.分析下列算法suanfa1(n): void suanfa1(int n) { int i,j,x=1； for(i=0；i数据结构模拟题(开卷)
数据结构模拟试题及答案
计算机专业基础综合(数据结构)模拟试卷1
数据结构复习模拟题5
数据结构模拟试题1
2018计算机考研：计算机数据结构测试题(四)
《数据结构C》模拟试题
《数据结构》模拟试卷一及答案
[考研类试卷]计算机专业基础综合数据结构(概论)历年真题试卷汇编2.doc
大工数据结构课程考试模拟试卷a
数据结构模拟试题9
计算机专业基础综合数据结构(概论)历年真题试卷汇编3
数据结构模拟试卷(含答案)
数据结构模拟卷(含答案)经典习题培训讲学
数据结构模拟试题一及答案汇编
数据结构期末模拟试题05(有答案)
数据结构模拟题(开卷)
相关主题
文本预览