数据结构复习答案2013-1
数据结构复习答案
一、选择填空
1.下面关于线性表的叙述中，错误的是哪一个？（）
A）线性表采用顺序存储，必须占用一片连续的存储单元。
√B）线性表采用顺序存储，便于进行插入和删除操作。
C）线性表采用链接存储，不必占用一片连续的存储单元。
D）线性表采用链接存储，便于插入和删除操作。
2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用
（）存储方式最节省时间。
√A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表
3.链表不具有的特点是（）。
A）插入、删除不需要移动元素√B）可随机访问任一元素
C）不必事先估计存储空间D）所需空间与线性长度成正比
4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度
为（）(1<=i<=n+1)。
A）O(0) B）O(1) √C）O(n) D）O(n2)
5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。
A）O(i) B）O(1) √C）O(n) D）O(i-1)
6.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）
A）head==NULL B）head→next==NULL√C）head→next==head D）head!=NULL
7.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。
A）p->next=s;s->next=p->next; √B）s->next=p->next;p->next=s;
C）p->next=s;p->next=s->next; D）p->next=s->next;p->next=s;
8.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( )。
√A）p->next=p->next->next B）p=p->next
C）p=p->next->next D）p->next=p
9.( )又称为FIFO表；( )又称为FILO表。
√A）队列B）散列表√C）栈D）哈希表
10.对于栈操作数据的原则是（）。
A）先进先出√B）后进先出C）后进后出D）不分顺序
11.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则
在进行删除操作时( )。
√A）仅修改队头指针B）仅修改队尾指针
C）队头、队尾指针都要修改D）队头、队尾指针都可能要修改
12.假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素
个数为（）。
√A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m 13.栈和队列的共同点是（）。
A）都是先进先出B）都是先进后出
√C）只允许在端点处插入和删除元素D）没有共同点
14.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈
后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A）6 B）4 √C） 3 D）2
15.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储
地址为1，每个元素占一个地址空间，则a85的地址为（）。
A）12 √B）33 C）18 D）40
16.由3 个结点可以构造出多少种不同的二叉树？( )
A）2 B）3 C）4 √D）5
17.二叉树中第i(i≥1)层上的结点数最多有( )个。
A）2i B）2i√C）2i-1D）2i-1
18.在有n个叶子结点的哈夫曼树中，其结点总数为( )。
A）不确定B）2n C）2n+1 √D）2n-1
19.一棵二叉树高度为h，所有结点的度或为0、或为2，则这棵二叉树最少有( )结点。
A）2h √B）2h-1 C）2h+1 D）h+1
20.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。
A）9 √B）11 C）15 D）不确定
21.树的后根遍历序列等同于该树对应的二叉树的( )。
A）先序序列√B）中序序列C）后序序列D）层序序列
22.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )。
A）都不相同√B）完全相同
C）先序和中序相同，而与后序不同D）中序和后序相同，而与先序不同
23.下列哪一种图的邻接矩阵是对称矩阵？( )
A）有向图√B）无向图C）AOV网 D）AOE网
24.在一个无向图中，所有顶点的度数之和等于所有边数( 2 )倍，在一个有向图中，所有顶点的
入度之和等于所有顶点出度之和的( 1 )倍。
A）1/2 √B）2 √C）1 D）4
25.一个有n个顶点的无向图最多有( )条边。由n个顶点组成的有向图，最多可以有( )条边。
A）n*n B）2n √C）n(n-1) √D）n(n-1)/2
26.下列说法不正确的是( )。
A）图的遍历是从给定的源点出发每一个顶点仅被访问一次
B）遍历的基本算法有两种：深度遍历和广度遍历
√C）图的深度遍历不适用于有向图
D）图的深度遍历是一个递归过程
27.下面哪一方法可以判断出一个有向图是否有环(回路) ( )。
A）深度优先遍历√B）拓扑排序C）求最短路径D）求关键路径
28.下列算法中，( )算法用来求图中每对顶点之间的最短路径。
A）Dijkstra √B）Floyed C）Prim D）Kruskal
29.关键路径是事件结点网络中( )。
√A）从源点到汇点的最长路径B）从源点到汇点的最短路径
C）最长回路D）最短回路
30.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记
录，其平均查找长度ASL为( )。
A）(n-1)/2 B）n/2 √C）(n+1)/2 D）n
31.下面关于二分查找的叙述正确的是() 。
A）表必须有序，表可以顺序方式存储，也可以链表方式存储
B）表必须有序，而且只能从小到大排列
C 表必须有序且表中数据必须是整型，实型或字符型
√D）表必须有序，且表只能以顺序方式存储
32.折半查找的时间复杂性为() 。
A）O(n2)B）O(n)C）O(nlogn)
√D）O(logn)
33.当采用分快查找时，数据的组织方式为() 。
A）数据分成若干块，每块内数据有序
√B）数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块
C）数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块
D）数据分成若干块，每块(除最后一块外)中数据个数需相同
34.下面关于哈希(Hash，杂凑)查找的说法正确的是()。
A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B）除留余数法是所有哈希函数中最好的
√C）不存在特别好与坏的哈希函数，要视情况而定
D）若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可35.下面给出的四种排序法中( )排序法是不稳定性排序法。
A）插入B）冒泡C）二路归并√D）堆
36.稳定的排序方法是( ) 。
A）直接插入排序和快速排序√B）折半插入排序和起泡排序
C）简单选择排序和四路归并排序D）树形选择排序和shell排序
37.有一组数据(15，9，7，8，20，-1，7，4) 用快速排序的划分方法进行一趟划分后数据的排序
为( )(按递增序)。
√A）下面的B，C，D都不对。 B）9，7，8，4，-1，7，15，20
C）20，15，8，9，7，-1，4，7 D）9，4，7，8，7，-1，15，20
38.设有一个文件有200个记录，按分块查找法查找记录，如分成10块，每块20个记录，用二分
查找法查索引表，用顺序查找法查块内记录，则平均查找长度为( )。
A）8）4 B）10）5 C）13）4 √D）16
39.快速排序在最坏情况下的时间复杂性为( )。
A）O(nlog2n) √B）O(n2) C）O(n) D）O(nlogn)
二、填空
1.一个算法的效率可分为时间效率和空间效率。
2.线性表L=（a1,a2,…,an）用数组表示，假定插入、删除表中任一元素的概率相同，则插入、删
除一个元素平均需要移动元素的个数是n/2和(n-1)/2。
3.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为
O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n) 。
4.顺序存储结构是通过元素在计算机内“物理位置相邻”表示元素之间的逻辑关系的，链
式存储结构是通过指针表示元素之间的逻辑关系的。
5.带头结点的双循环链表L为空表的条件是：p-next=head 。
6.当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top1与top2，则当
栈1空时，top1为 1 ，栈2空时，top2为n ，栈满时为top1+top2==n。
7.顺序栈S用data[1））n]存储数据，栈顶指针是top，则值为x的元素入栈的操作是*S）
top++=x 。
8.已知链队列Q的头尾指针分别是f和r，则将值x入队的操作序列是
p->data=e;p->next=NULL;Q）r->next=p;Q）r=p;。
9.稀疏矩阵的存储策略是只存储非零元素。
10. 稀疏矩阵的存储方法主要有两个：一个是 三元组 ，另一个是十字链表示法。
11. 二叉树由 根 ， 左子树 、 右子树 三个基本单元组成。 12. 一棵有n 个结点的满二叉树有 n 1=0 个度为1的结点、有 (n-1)/2, (n 1+2n 2)个分支 (非终
端)结点和 (n=n 0+n 1+n 2, n 0= n 2+1), (n+1)/2 个叶子，该满二叉树的深度为log 2(n+1) 。
13. 设F 是由T1,T2,T3三棵树组成的森林，与F 对应的二叉树为B ，已知T1,T2,T3的结点数分别
为n1，n2和n3则二叉树B 的左子树中有 n1-1 个结点，右子树中有 n2+n3 个结点。 14. 线索二叉树的左线索指向其 前驱 右线索指向其 后继 。 15. 设一棵Huffman 树有6个叶结点，权值分别为3、4、7、14、15、20，则根节点的权值是 63 。
当 初始记录序列按关键字有序或基本有序 时，快速排序算法的时间复杂性为O(n 2
)。 16. 在有n 个结点的二叉链表中，空链域的个数为 n+1 。
17. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个
度为2的结点，有 1 个度为1的结点。
18. 若用n 表示图中顶点数目，则有 n*(n-1)/2 条边的无向图成为完全图。 19. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di(1<=i<=n 〉，则e=∑=n
i di 1
2
/1。
20. 在有n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要 n*(n-1) 条弧。 21. 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的
度 ；对于有向图来说等于该顶点的 出度 。
22. 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次；当使用监
视哨时，若查找失败，则比较关键字的次数为 n+1 。
23. 在顺序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查找关键码值20，需做的关键码
比较次数为 4 。
24. 对于长度为255的表，采用分块查找，每块的最佳长度为 16 。
25. 已知二叉排序树的左右子树均不为空，则 左子树 上所有结点的值均小于它的根结点值，
右子树 上所有结点的值均大于它的根结点的值。
26. 动态查找表和静态查找表的重要区别在于前者包含有 插入 和 删除 运算，而后者
不包含这两种运算。
27. 为了能有效地应用HASH 查找技术，必须解决的两个问题是 设计一个好的哈希函数 和 选择一个处理冲突的方法 。
28. 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 比较 和记录
的 移动 。
29. 属于不稳定排序的有 希尔、快速、选择、堆排序 。
30. 快速排序算法的时间复杂度为 O(n 2
) 。
三、应用题
1. 试画出下列稀疏矩阵的三元组表示。
稀疏矩阵
2. 二叉树有哪几种基本形态? 画图说明之。 解答：5种。
i j v 1 3 18 2 1 3 3
4 24 5
3
66
A
A A
A
－
+ c a b *
/
d e NULL
3. 写出下列二叉树的前序，中序，后序遍历序列及对应的森林。
解答：前序：- + a * b c / d e
中序：a + b * c - d / e 后序：a b c * + d e / -
4. 试将森林 F={ T1,T2,T3,T4 }转换为一棵二叉树。
T1 T2 T3 T4 解答：
5. 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。
解答：
L=4*2+3+3*2=17
-
+ / a * d
e
b c
F
D G E
H K J
C B
I
A
L M
N O
P Q
1 5 6 9 11 21
15
36
6. 设一棵树T 中边的集合为{(A ，B)，(A ，C)，(A ，D)，(B ，E)，(C ，F)，(C ，G)}，要求用孩
子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。 解
答：
7. 已知有向图G=(V ,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
8. 有7个顶点（v1,v2,v3,v4,v5,v6,v7） 的有向图的邻接矩阵如右图。请回答相关问题： （1）
解答：
（2） 写出从v1出发的深度优先遍历和广度优先遍历序列。 深度优先遍历：V1 V2 V6 V7 V3 V4 V5
广度优先遍历：V1 V2 V3 V4V6 V5 V7
9. 已知如图所示的有向图，请给出该图的:
∞ 2 5 3 ∞ ∞ ∞ ∞ ∞ 2 ∞ ∞ 8 ∞ ∞ ∞ ∞ 1 3 5 ∞ ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 3 9 ∞ ∞ ∞ ∞ ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ ∞
（1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表；
（4） 逆邻接表。
10. 设无向图G （所下图所示），要求给出该图的深度优先和广度优先遍历的序列，找出下面
网络的最小生成树。
解答：
深度优先:：A B D F C E G 广度优先： A B D C E F G
11. 分别说明Huffman 算法、Dijkstra 算法、Prim 算法、Kruskal 算法的功能。 解答：
Huffman 算法：最优二叉树，树的带权路径最短。 Dijkstra 算法：求单源最短路径 Prim 算法：求最小生成树 Kruskal 算法：求最小生成树
顶点 1 2 3 4 5 6 入度 3 2 1 1 2 2 出度 0
2
2
3
1
3
∞ ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ 1 ∞ ∞ ∞ 1 ∞ ∞ ∞ 1 ∞ ∞ 1 ∞ 1 1 1 ∞ ∞ ∞ ∞ ∞ 1 1 ∞ ∞ 1 ∞
邻接矩阵
0 1 ∧
1 2 -> 0 -> 3 ∧
2 3 -> 1 -> 5 ∧
3 4 -> 2 -> 5 -> 6 ∧
4 5 -> 0 ∧
5 6 -> 0 -> 1 -> 4 ∧
邻接表
0 1 -> 1 -> 4 -> 5 ∧ 1 2 -> 2 -> 5 ∧ 2 3 -> 3 ∧ 3 4 -> 1 ∧ 4 5 3 -> 5 ∧ 5 6 -> 2 -> 3 ∧ 逆邻接表
A
B E D
C F G 3 1
5
5
5
4
12. 已知图G 如图所示。 （1） 画出图G 的邻接表；
（2） 画出从顶点1出发的深度优先生成树和广度优先生
成树；
（3） 写出图G 的拓扑排序列； 解答：（1） 0 1 －> 1 －> 2 －> 3 ∧ 1 2 －> 4 ∧
2 3 －> 4 －> 5 ∧ 3 4 －> 5 ∧
4 5 －> 5 －> 6 ∧ 5 6 －> 6 ∧ 6
7
∧
（2） （3）1，2，3，4，5，6，7
13. 已知AOE 网如下，试求其关键路径。要求写出计算过程。
解答：
14. 设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题：
（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度。
（2）按表中元素的顺序进行插入生成一棵AVL 树，画出该树。并求出在等概率情况下查找成功的平均查找长度。 解答： （1）
ASL=(1+2*2+3*3+4)/12=18/7
1 2 3 4 5 6
ve 0 4 3 8 7 10
vl 0 4 4 8 9 10
1
2 4 5
7 6 3 4
2 5
1 3
7
（
15. 假定一个线性表为L=（18，75，60，43，54，90，46，31，58，73，15，34）进行散列存
储，采用的Hash 函数为H （K ）=K mod 13 ，当发生冲突时用线性探测法处理冲突，设Hash 表的表长为13，试构造Hash 表，并求出平均查找长度。 解答：
16. 用快速排序方法对下列整数序列进行排序，写出中间及最后结果。
[89,27,52,90,15,28,100,72]
解答：
一趟：89 [72,27,52, 28,15, 89,100, 90]
二趟：72 [15,27,52, 28, 72] 89 [100, 90] 三趟：15 [,27,52, 28] 72 89 [100, 90] 四趟：15 27 [,52, 28] 72 89 [100, 90] 五趟：15 27 [28, 52] 72 89 [100, 90] 六趟：15 27 28 52 72 89 [90, 100]
17. 序列{40，38，60，95，76，10，25，50，99}是堆吗？若不是，创建一个堆。
四、算法设计题
1.已知L为带头结点的单链表，设计一个算法计算数据域为x的结点个数。
int count(LinkList La,ElemType x){
//计数x出现的次数
LinkList p=La->next; //p为工作指针
int n=0;
while(p){
if(p->data ==x) n++;
p=p->next ;
}
return n;
}
2.设L为有序顺序表，试编写一个算法删除L中的重复元素。要求不要另开辟数据存储空间。
例如：L=（1，1，2，4，4，9，9，9），执行算法后L=（1，2，4，9）
int delduplicate(int a[],int n){
int i,j,k,count;
i=0;
while (i j=i+1; count=0; while (j j++; count++; } if (count!=0){ for(k=j;k } n=n-count;i++; } return n; } 3.假设一个人算术表达式包含圆括弧，编写一个判别表达式中括弧是否正确匹配的算法。 Status matching(SqStack S,string exp) { int state = 1; int i=0; SElemType e; while(i { switch(exp[i]) { case '(': { push(S,exp[i]); break; } case ')': { if(!StackEmpty(S) && (GetTop(S,e),e=='(')) { pop(S,e); } else state = 0; break; } } i++; } if (StackEmpty(S) && state) return OK; else return ERROR; } 4.设二叉树采用二叉链表法存储，试编写一个求二叉树深度的算法。 //求二叉树的深度 int Depth (BiTree &T ){ // 返回二叉树的深度 int depthval,depthLeft,depthRight; if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild ); depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight); } return depthval; } 5.编写算法,求二叉树中度为2结点个数。 void Countdu2 (BiTree &T, int &count){ //统计二叉树中度为2结点的个数if ( T ) { if ((T->lchild)&& (T->rchild)) count++; // 对度为2的结点计数 Countdu2( T->lchild, count); Countdu2( T->rchild, count); } // if } // Countdu2 6.编写算法,求二叉树中叶结点个数。 //统计二叉树中叶子结点的个数 void CountLeaf (BiTree &T, int &count){ i f ( T ) { if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if } // CountLeaf 《数据结构》复习题及答案 一、判断题 1．线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（√）2．一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（ㄨ） 3．稀疏矩阵压缩存储后，必会失去随机存取功能。（√） 4．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（√）5．用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（√） 6．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（ㄨ） 7．逻辑结构与数据元素本身的内容和形式无关。（√）1．设无向图G（所下图所示），要求给出从1出发对该图进行深度优先和广度优先遍历的序列。 8．对链表进行插入和删除操作时不必移动链表中结点。( √ ) 9．如果两个串含有相同的字符，则说明它们相等。( ㄨ ) 10．在线索二叉树中，任一结点均有指向其前趋和后继的线索。( ㄨ) 11．带权无向图的最小生成树是唯一的。（ㄨ） 12．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（√）13．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。( ㄨ ) 14．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（√）15．由树转化成二叉树，该二叉树的右子树不一定为空。（ㄨ） 16．稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（√）17．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（√）18．设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（ㄨ）19．每种数据结构都具备三个基本操作：插入、删除和查找。（ㄨ） 20．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（×） 二、单项选择题 1．下面关于线性表的叙述错误的是（ D ）。 A 线性表采用顺序存储必须占用一片连续的存储空间 B 线性表采用链式存储不必占用一片连续的存储空间 C 线性表采用链式存储便于插入和删除操作的实现 D 线性表采用顺序存储便于插入和删除操作的实现 2．单链表的存储密度（ C ）。 A．大于1 B．等于1 C．小于1 D．不能确定 3．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。 A 5，3，4，6，1，2 B 3，2，5，6，4，1 C 3，1，2，5，4，6 D 1，5，4，6，2，3 4．若串S="SOFTWARE"，其子串的数目最多是：（ C ）。 A．35 B．36 C．37 D．38 数据结构复习答案 一、选择填空 1.下面关于线性表的叙述中，错误的是哪一个？（） A）线性表采用顺序存储，必须占用一片连续的存储单元。 √B）线性表采用顺序存储，便于进行插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用链接存储，便于插入和删除操作。 2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用 （）存储方式最节省时间。 √A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表 3.链表不具有的特点是（）。 A）插入、删除不需要移动元素√B）可随机访问任一元素 C）不必事先估计存储空间D）所需空间与线性长度成正比 4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度 为（）(1<=i<=n+1)。 A）O(0) B）O(1) √C）O(n) D）O(n2) 5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。 A）O(i) B）O(1) √C）O(n) D）O(i-1) 6.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（） A）head==NULL B）head→next==NULL√C）head→next==head D）head!=NULL 7.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A）p->next=s;s->next=p->next; √B）s->next=p->next;p->next=s; C）p->next=s;p->next=s->next; D）p->next=s->next;p->next=s; 8.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( )。 √A）p->next=p->next->next B）p=p->next C）p=p->next->next D）p->next=p 9.( )又称为FIFO表；( )又称为FILO表。 √A）队列B）散列表√C）栈D）哈希表 10.对于栈操作数据的原则是（）。 A）先进先出√B）后进先出C）后进后出D）不分顺序 11.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则 在进行删除操作时( )。 √A）仅修改队头指针B）仅修改队尾指针 C）队头、队尾指针都要修改D）队头、队尾指针都可能要修改 12.假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素 个数为（）。 √A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m 13.栈和队列的共同点是（）。 A）都是先进先出B）都是先进后出 √C）只允许在端点处插入和删除元素D）没有共同点 14.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈 后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A）6 B）4 √C） 3 D）2 15.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储 一、填空 1、一种数据结构的二元组表示如下： K={a,b,c,d} R=(a,b),(b,c),(c,d),(a,d)} 此数据结构是图。 2、在定义某种数据结构时，其数据域的数据类型可分为简单类型和结构体类型两种，为增强其通用性，应将其再定义为通用数据类型。 3、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为1：N 、M：N 。 4、数据结构简单地说是指数据以及相互之间的联系。 5、算法应具备以下5个特性：有穷性、正确性、可行性、输入和输出。 6、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是处理问题的样本量。 7、在稀疏矩阵中，非零元素的个数远远少于零元素的个数。 8、的运算规则为后进先出，队列的运算规则为先进先出。 9、对于一个单链表在表头插入结点的时间复杂度为O(1) ，在表尾插入元素的时间复杂度为O(n) 。 10、在单链表中每个结点包含二个域，一个叫值域（或data），另一个叫指针域(或*next)。 11、顺序表中用数组存储线性表。 12、在顺序表中删除一个元素，必须执行的语句是：size - - 。 二、选择题 1、下面程序段的时间复杂度为（ B ）。 for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) printf(“%d*%d=%d\n”,i,j,i*j); 1 A．O(n) B. O(n2) C．O(1) B. O(n3) 2、顺序表物理结构中的存储单元（ A ）。 A. 一定是连续的 B. 一定是不连续的 C. 不一定是连续的 D. 经删除操作后不连续 3、对一个顺序存储结构的栈，栈满的判断条件是（ D ） A.S.top= =-1 B.S.top= =0 C.S.top= =MaxSize D. S.top= =MaxSize-1 4、若循环队列有n个顺序存储单元，front、rear分别为队首和队尾指针则判断队满的条件是(C) A. (front+1)%n= =rear B. (front-1)%n= =rear C.(rear+1) %n= =front D. (rear-1)%n= = front 5、下列是顺序存储线性表排序的算法 void Sort(List& L) { int i,j; ElemType x; for(i=1;i 试卷代号:1252 中央广播电视大学2013-2014学年度第一学期“开放学科”期末考试 数据结构（本）试题 2014年1月 一、单项选择题（每小题2分，共30分） 1. 在数据结构和算法中，与所使用的计算机有关的是（B）。 A．数据元数间的抽象关系 B．数据的存储结构 C．算法的时间复杂度 D．数据的逻辑结构 2.对顺序表,以下叙述中正确的是 ( A )。 A．用一组地址连续的存储单元依次存放线性表的数据元素 B．各个数据元素的首地址是连续的 C．数据元素不能随机访问 D．插入操作不需要移动元素 3．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（C）。 A．9 B．10 C．15 D．16 4. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为 ( A)。 A.p->next=p->next->next; B.p=p->next; C.p=p->next->next; D.p->next=p ; 5．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（A）。（进栈出栈可以交替进行）。 A．7，5，3，1 B．7，3，1,5 C．7，5，1，3 D．5,1，3，7 6．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（C）。 A．p=top->next; top=top next; B．p->next=top; C．p->next=top;top=p; D．top=p; 7．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（D）。(矩阵中的第1个元素是a1,1） A．a7,6 B．a10,8C．a9,2 D．a8,5 8．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储 到一维数组B中（数组下标从1开始），则矩阵中元素a10,6在一维数组B中的下标是（C）。(矩阵中的第1个元素是a1,1） A．45, B．18 C．51 D．53 9．串函数StrCmp（“ABCd”，“ABCD”）的值为（C）。 A．0 B．-1 C．1 D．3 10．一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有（C）个结点。 A．n+1 B．n C．n-1 D．n-2 2013年1月高等教育自学考试全国统一命题考试 数据结构试题 课程代码：02331 考生答题注意事项： 1.本卷所有试卷必须在答题卡上作答。答在试卷和草稿纸上的无效。 2.第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3.第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹笔作答。 4.合理安排答题空间，超出答题区域无效。 选择题部分 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．数据的逻辑结构可以分为 A．动态结构和静态结构 B.顺序结构和链式结构 C．线性结构和非线性结构 D.简单结构和构造结构 2．线性表是一个有限序列，组成线性表的基本单位是 A．数据项 B.数据元素 C．数据域 D.字符 3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可 ．．能．的出栈序列是 A．dcba B.cbda C．cadb D.cdba 4．稀疏矩阵的三元组表是 A．顺序存储结构 B.链式存储结构 C．索引存储结构 D.散列表存储结构 5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是 A．5 B.6 C．7 D.8 6．下列编码集合中，属于前缀编码的一组是 A.{11,10,001,101,0001} B.{00,010,0110,1000} C.{11,01,001,0101,0001} D.{0,10,110,1011} 7.如题7图所示二叉树的中序序列为 A．ACDB B．DCBA C．CDBA D．ABCD 题7图 8．有向图中所有顶点入度之和与所有顶点出度之和的比是 A．1/2 B.1 C．2 D.4 9．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是 A.e B.2e C.n2-2e D.n2-e 10.n个顶点的无向连通图，其生成树的边数为 A.n-l B.n C.n+l D.nlogn 11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为 A．2 B.3 C．4 D.5 12．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是 A.(13,44,55,26,8,29) B.(13,26,55,44,8,29) C.(8,13,26,29,44,55) D.(29,26,8,44,55,13) 13．采用分块查找时，要求数据 A．块内有序 B.分块有序 C．分块无序 D.每块中数据个数必须相同 14.下列关于散列函数的说法正确的是 A．散列函数越复杂越好 B.散列函数越简单越好 C．用除余法构造的散列函数是最好的 D.在冲突尽可能少的情况下，散列函数越简单越好 15.下列关于m阶B树的叙述中，错误 ．．的是 A．每个结点至多有m棵子树 一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n）C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p 第一部分：数据结构——线性结构(顺序表、链表、栈、队列、数组、串) 考点： 1、时间复杂度 2、数据的逻辑结构与存储结构相关知识——分类、与存储结构之间的关系 3、顺序表的知识——特点 4、链表的知识——编程求单链表中结点的个数、插入、删除。 5、栈与队列知识——特点、循环队列、基本术语、链队列 6、数组与矩阵——求元素的地址、稀疏矩阵 行优先存储: 下标从1开始: Loc(A i,j) = Loc(A1,1)+[(i-1)*n+j-1]*b 下标从0开始: Loc(A i,j) = Loc(A0,0)+(i*n+j)*b 列优先存储: 下标从1开始: Loc(A i,j) = Loc(A1,1)+[(j-1)*m+i-1]*b 下标从0开始: Loc(A i,j) = Loc(A0,0)+(j*m+i)*b 1. 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___________个数据元素；删除第i个位置上的数据元素需要移动表中___________个元素。 2.数据的逻辑结构通常有集合、线性结构、_________ 和 _________ 四类结构。 3.若进栈序列为a、b、c ，且进栈和出栈可以穿插进行，则可能出现_________个不同的出栈序列。 4.在栈结构中，允许插入的一端称为 _________；在队列结构中，允许删除的一端称为 _________。 5. 下列程序段的时间复杂度为_____________ s=0; for(i=1;i 1 第一章概论 习题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为（D, R ），其中D 是 数据元素 的有限集合，R 是D 上的 关系 有限集合。 3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。 10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。 11. 一个算法的效率可分为 时间 效率和 空间 效率。 二、单项选择题 （ B ）1. 非线性结构是数据元素之间存在一种： A ）一对多关系 B ）多对多关系 C ）多对一关系 D ）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构； A) 存储 B) 物理 C) 逻辑 D) 物理和存储 （ C ）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （ A ）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （ B ）6. 计算机算法必须具备输入、输出和 等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题 1.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。 2. 简述线性结构与非线性结构的不同点。 答：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。 四、【严题集1.8④】分析下面各程序段的时间复杂度 2. s=0; for i=0; i 数据结构复习题及参考答案 （抽考其中50%） 一、单选题(每小题1分) 1．下列程序段的时间复杂度为（A ）。 for(i=0； i 13-14-1《数据结构》复习题 2013.12. 一、判断题 1. 边数很少的稀疏图，适宜用邻接矩阵表示。（×） 2. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。(×) 3. 有回路的有向图不能完成拓扑排序。( √ ) 4. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。( √ ) 5. 一个无向连通图的生成树是图的极小的连通子图。（√） 6. 哈希查找法中解决冲突问题的常用方法是除留余数法。（×） 7. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带 来方便。(√) 8. 对判定树进行中根遍历，可得到结点的有序序列。（√） 9. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。（√） 10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。（√） 11. 在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作 为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。( × ) 12. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。( √ ) 13. 边数很少的稀疏图，适宜用邻接表表示。（√） 14. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（√） 15. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后 序遍历，则具有相同的结果。( √ ) 16. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（×） 17. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间 复杂度为O(log2n)。( × ) 18. 如果有向图中各个顶点的度都大于2，则该图中必有回路。( × ) 19. 对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑 有序的序列中。(×) 20. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。( √ ) 21. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( × ) 22. 内部排序是指排序过程在内存中进行的排序。（√） 23. 折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树。(√) 24. 循环链表的结点与单链表的结点结构完全相同，只是结点间的连接方式不同。（√）25．理想情况下哈希查找的等概率查找成功的平均查找长度是O（1）。（√） 二、单项选择题 1. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（B）。 A.HS->next=s; B.s->next=HS->next;HS->next=s; C.s->next=HS;HS=s; D.s->next=HS;HS=HS->next; 2. 已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成 一棵二叉排序树后，最后两层上的结点总数为（B）。 A. 1 B.2 C.3 D.4 3. 在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时（ B ）。 1.6 习题 1.6.1知识点：数据结构的定义 一、选择题 1①数据结构通常是研究数据的（ A ）及它们之间的相互联系。 A．存储和逻辑结构B．存储结构C．顺序结构D．链式存储结构 2①数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ） A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 3①线性结构是数据元素之间存在一种（D ）。 A．一对多关系 B. 多对多关系 C 多对一关系D 一对一关系 4①计算机内部数据处理的基本单位是（ B ）。 A. 数据B．数据元素 C.数据项D．数据库 5②从逻辑上可以把数据结构分为（C ）两大类。【武汉交通科技大学1996】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 二、填空题 1①数据结构按逻辑结构可分为四大类，它们分别是集合、线性、树、图。 2①数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、散列、索引。 三、判断题 （F）1①数据元素是数据的最小单位。 （T ）2①记录是数据处理的最小单位。 （ F ）3①数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （T ）4①数据的物理结构是指数据在计算机内的实际存储形式。 四、简答题 1①简述什么是数据结构? 2②数据结构与数据类型有什么区别? 【哈尔滨工业大学2001】 1.6.2知识点：算法的概念 一、选择题 1①计算机算法指的是（C ） A．计算方法B．排序方法 C．解决问题的有限运算序列D．调度方法 2①算法分析的目的是（（1）C ），算法分析的两个主要方面（（2）A ）． 绝密★考试结束前 全国2013年1月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.数据的基本单位是 A.数据元素 B.数据项 C.字段 D.域 2.算法的空间复杂度是指 A.算法中输入数据所占用的存储空间的大小 B.算法本身所占用的存储空间的大小 C.算法中所占用的所有存储空间的大小 D.算法中需要的辅助变量所占用存储空间的大小 3.从一个长度为100的顺序表中删除第30个元素,需向前移动的元素个数为 A.29 B.30 C.70 D.71 4.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是 A.单链表 B.双链表 C.单循环链表 D.顺序表 5.判断链栈LS是否为空的条件是 C.LS! =NULL D.LS= =NULL 6.关于链队列的运算说法正确的是 A.入队列需要判断队列是否满 B.出队列需要判断队列是否空 C.入队列需要判断队列是否空 D.出队列需要判断队列是否满 7.元素的进栈次序为A,B,C,D,E,则出栈中不可能 ．．．的序列是 A.A,B,C,D,E B.B,C,D,E,A C.E,A,B,C,D D.E,D,C,B,A 8.具有63个结点的完全二叉树是 A.满二叉树 B.二叉排序树 C.哈夫曼树 D.空树 9.将含有80个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是 A.左孩子编号为79，右孩子编号为80 B.左孩子不存在，右孩子编号为80 C.左孩子编号为80，右孩子不存在 D.左孩子不存在，右孩子不存在 10.将题10图所示的一棵树转换为二叉树，结点D是 A.A的右孩子 B.B的右孩子 C.C的右孩子 D.E的右孩子 11.无向图的邻接矩阵是题10图 A.对称矩阵 B.稀疏矩阵 C.对角矩阵 D.上三角矩阵 12.图的广度优先搜索遍历的过程类似于树的 A.前序遍历 B.中序遍历 C.后序遍历 D.按层次遍历 13.要解决散列引起的冲突问题，最常用的方法是 A.数字分析法、除留余数法、平方取中法 B.除留余数法、线性探测法、平方取中法 C.线性探测法、二次探测法、链地址法 D.除留余数法、线性探测法、二次探测法 14.下列表述中，正确的是 A.序列（102，81，55，62，50，40，58，35，20）是堆 《数据结构》期末复习题及参考答案 - 第6章 树和二叉树 一、 选择题 1、在二叉树的第I 层(I≥1)上最多含有结点数为（ ） A. 2I B. 2I-1-1 C. 2I-1 D. 2I -1 2、深度为6的二叉树最多有( )个结点 A ．64 B.63 C.32 D.31 3、一棵树高为K 的完全二叉树至少有( )个结点 A.2k –1 B.2k-1 –1 C.2k-1 D.2 k 4、有关二叉树下列说法正确的是（ ） A. 二叉树的度为2 B. 一棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 5、n 个结点的线索二叉树上含有的线索数为（ ） A. 2n B. n －l C. n ＋l D. n 6、线性表和树的结构区别在于（ ） A ．前驱数量不同，后继数量相同 B ．前驱数量相同，后继数量不同 C ．前驱和后继的数量都相同 D ．前驱和后继的数量都不同 7、已知一算术表达式的中缀形式为 A+B*C-D/E ，后缀形式为ABC*+DE/-，则其前缀形式 为( ) A ．-A+B*C/DE B. -A+B*CD/E C ．-+*ABC/DE D. -+A*BC/DE 8、设有一表示算术表达式的二叉树（见下图）， 它所表示的算术表达式是（ ） A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) 9、一棵具有 n 个结点的完全二叉树的树高度（深度）(符号⎣⎦x 表示取不大于x 的最大整数) 是（ ） 10、利用二叉链表存储树，则根结点的右指针是（）。 11、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历 的结果为（）。 12、某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是： 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．上面的都不对 13、若前序遍历二叉树的结果为序列A、B、C，则有_________棵不同的二叉树可以得到这 一结果。 A. 3 B. 4 C. 5 D. 6 14、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 则它的前序遍历是 （）。 A. acbed B. decab C. deabc D. cedba 15、线索二叉树是一种（）结构。 A．逻辑B．逻辑和存储C．物理D．线性 二、填空题 1、对于任意一棵二叉树，如果其叶子结点数为N0，度为1的结点数为N1，度为2的结点数为N2，则N0=___ N2 + 1_________。 4、深度为H 的完全二叉树至少有_ 2__个结点；至多有2-1_个结点；H和结点总数N 西安电子科技大学 考试时间 120 分钟 试题（A） 题号一二三四五六七八九十总分 分数 1.考试形式：闭卷；2。考试日期：2013年月日3.本试卷共四大题，满分100分。 班级学号姓名任课教师 一、单选题（15小题，每题2分，共30分） 1. 以下关于数据结构的描述正确的是（B ） A．数据的逻辑结构描述了数据项与数据项之间存在的某种关系 B．数据结构操作的实现与存储结构有关 C．数据的逻辑结构相同，对应的存储结构也相同 D．数据结构的抽象数据类型中操作的定义与存储结构有关 2. 关于算法的时间复杂度的描述正确的是（C ） A．时间复杂度相同的算法在相同的计算机上的运行时间相同 B．时间复杂度相同的算法在解决问题的规模相同时运行时间相同 C．算法的时间复杂度仅反映算法的运行时间与问题规模之间的关系 D．算法的时间复杂度与问题的规模和计算机硬件的运行速度相关 3. 在长度为n的顺序表的表尾插入一个新元素的时间复杂度为（B ） A．O(n) B．O(1) C．O(n2) D．O(log2n) 4. 已知单链表中结点*q是结点*p的直接前驱，若在*q与*p之间插入结点*s，需要执行的操作是（ A ） A．s->next= q->next; q->next=s; B．s->next=p->next; p->next=s; C．q->next=s; s->next= q->next; D．p->next=s; s->next=q; 5. 下列哪种操作利用到了栈的结构（A ） A．递归函数调用B．树的层次遍历 C．顺序查找D．选择排序 6．设有一个n×n的对称矩阵A的下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A中的元素A[i][j]存放于B中的存放位置是（A ） A．(i+1)*i/2+j B．(i+1)*j/2+j | | | | | | | |装| | | | |订| | | | | |线| | | | | | | | | 数据结构试卷（B）期末考试标准答案及评分细则一、 选择题（本大题共15小题，每题2分，共30分。） 1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ C ）。 A 数据的处理方法 B 数据元素的类型 C 数据元素之间的关系 D 数据的存储方法 2、算法的时间复杂性是（ C ）。 A简单操作次数的多少 B 算法运行时间的多少 C 一个算法运行时间的相对度量D数据处理时间的多少 3、下列关于顺序存储结构的叙述中，不正确的是（C ）。 A 结点之间的关系由存储单元的邻接关系来体现 B存储密度大，存储空间利用率高 C 插入、删除操作灵活方便，不必移动结点 D 可以通过计算机直接确定第i个结点的存储地址 4、栈中元素的进出原则是（ B ）。 A 先进先出B后进先出C栈空则进D栈满则出 5、一个队列的入队顺序是w,x,y,z,，则队列的输出顺序是（ A ）。 A w,x,y,z B z,y,x,w C w,z,x,y D x, y,z,w 6、稀疏矩阵一般的压缩存储方式有两种，即（C ）。 A 二维数组和三维数组 B 三元组和散列 C 三元组和十字链表 D 散列和十字链表 7、设有一个5阶的对称矩阵array采用按行优先压缩存储，array[0][0]为第一个元素，其存储地址为1000，每个元素占3个存储单元，则元素A[4][4]的存储地址为（ A ）。 A 1042 B 1052 C 1056 D 1092 8、用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有右子树，则右子树的根结点是（ B ）。A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 9、设二叉树有n个结点，则其深度为（ D ）。 A n-1 B n C ⎣log2n⎦ +1 D 不能确定 10、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（B ）倍。 A 1/2 B 1 C 2 D 4 11、有9个结点的无向图最多有（ B ）条边。 A 18 B 36 C 72 D 144 12、静态查找与动态查找的根本区别在于（ B ）。 A 它们的逻辑结构不一样B施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 13、对线性表进行折半查找时，要求线性表必须（ C ）。 A 以链接方式存储且结点按关键字有序排列 B 以顺序方式存储 C 以顺序方式存储且结点按关键字有序排列D以链接方式存储 14、在排序方法中，从未排序的序列中依次取出数据元素与已排序的序列（初始时为空）中的数据元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ C ）。 A希尔排序B冒泡排序C直接插入排序D选择排序 15、（ D ）方法是从未排序序列中挑选元素，并将其放入已排序序列的一端。 A 归并排序 B 插入排序 C 快速排序 D 选择排序 二、 填空题（本大题共9小题，每空2分，共20分。） 1、一个算法的效率可分为时间效率和空间效率。 2、不带头结点的单链表，其头指针为head，判断单链表为空的条件是head ==NULL 。 3、在一个长度为n的顺序表中删除第i个元素时，1<=i<=n，需向前移动n-i 个元素。 4、在一棵高度为5的二叉树中，最多含有31 个结点，最少含有 5 个结点。 5、如果由有序树T转换得到的二叉树是T'，那么T中结点的后序序列就是T' 中结点的 中序序列。 6、有向图G用邻接矩阵存储，其第j列的所有元素之和等于顶点j的入度(之和) 。 7、n个顶点的生成树有n-1 条边。 8、具有n个结点的二叉排序树，其最大深度为n，最小深度为___⎣log2n⎦ +1____。 9、堆的形状是一棵完全二叉树。《数据结构》复习题及答案
数据结构复习答案2013-1
数据结构1-3章习题答案2013
数据结构1252本2013一2014学年度第一学期期末考试
02331数据结构2013年1 月份历年真题附答案
数据结构期末复习题及答案1
2013年-数据结构-复习题
数据结构 第1章 习题答案
数据结构复习资料(题目和参考答案)
数据结构复习题
数据结构第1章习题参考答案
2013年1月数据结构导论试题与答案
《数据结构》期末复习题及参考答案 - 第6章 树和二叉树【HSH2013级】给学生
2013 数据结构试题 (答案)
防灾科技学院数据结构2013-2014-1 B+答案最终版
- 2013年算法与数据结构文档.doc
- 院校资料-北京理工大学2013级数据结构B试题(A卷)-答案
- 数据结构真题2013年10月
- E__Temp2_2013数据结构试题
- 02142数据结构导论2013年10月份真题及答案
- 数据结构复习答案2013-1
- 数据结构练习题2012-2013
- 02331数据结构2013年10月份历年真题附答案
- 全国2013年1月高等教育自学考试数据结构试题
- 2013年山东科技大学数据结构与操作系统--真题及参考答案
- 2013年上海海事大学数据结构考研真题研究生入学考试试卷
- 2013年学位授予信息年报数据结构对应代码表
- 2013年算法与数据结构文档
- 02331数据结构 全国13年10月自考 试题
- 02331数据结构2012年10月份历年真题02331数据结构2013年1 月份历年真题附答案
- 数据结构课件(2013年)zy (1)
- 2013数据结构 学生信息管理系统-大二
- 2013年数据结构试题集(10套题并附带答案)
- 2013年数据结构试题集10套题并附带答案
- 数据结构(本)期末综合练习(2013年12月)