一、单选题(每小题 2 分,共 12 分)
“数据结构”期末考试试题
1.在一个单链表 HL 中,若要向表头插入一个由指针 p 指向的结点,则执行( )。
A. HL=ps p 一>next=HL
B. p 一>next=HL;HL=p3
C. p 一>next=Hl;p=HL;
D. p 一>next=HL 一>next;HL 一>next=p;
2.n 个顶点的强连通图中至少含有(
A.n—l 条有向边
C.n(n—1)/2 条有向边
3.从一棵二叉搜索树中查找一个元素时,其时间复杂度大致为(
A.O(1)
C.O(1Ogzn)
4.由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为(
A.24
C. 72
5.当一个作为实际传递的对象占用的存储空间较大并可能需要修改时,应最好把它说明为(
D.n(n 一 1)条有向边
B.n 条有向边
B.48
D. 53
B.O(n)
D.O(n2)
)。
)。
)。
)参数,以节省参数值的传
输时间和存储参数的空间。
A.整形
C.指针型
B.引用型
D.常值引用型·
6.向一个长度为 n 的顺序表中插人一个新元素的平均时间复杂度为(
)。
A.O(n)
C.O(n2)
B.O(1)
D.O(10g2n)
二、填空题(每空 1 分,共 28 分)
1.数据的存储结构被分为——、——、——和——四种。
2.在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为——域和——域。
3.——中缀表达式 3 十 x*(2.4/5—6)所对应的后缀表达式为————。
4.在一棵高度为 h 的 3 叉树中,最多含有——结点。
5.假定一棵二叉树的结点数为 18,则它的最小深度为——,最大深度为——·
6.在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定——该结点的值,右子树上所有结点的值一定——该结
点的值。
7.当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层——调整,直到被调整到——位置为止。
8.表示图的三种存储结构为——、——和———。
9.对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种遍历时,其时间复杂度为——,对用邻接表表示的图进行任一
种遍历时,其时间复杂度为——。
10.从有序表(12,18,30,43,56,78,82,95)中依次二分查找 43 和 56 元素时,其查找长度分别为——和——·
11.假定对长度 n=144 的线性表进行索引顺序查找,并假定每个子表的长度均为
度为——,时间复杂度为——·
12.一棵 B—树中的所有叶子结点均处在——上。
13.每次从无序表中顺序取出一个元素,把这插入到有序表中的适当位置,此种排序方法叫做——排序;每次从无序表中挑
,则进行索引顺序查找的平均查找长
选出一个最小或最大元素,把它交换到有序表的一端,此种排序方法叫做——排序。
14.快速排序在乎均情况下的时间复杂度为——,最坏情况下的时间复杂度为——。
三、运算题(每小题 6 分,共 24 分)
1.假定一棵二叉树广义表表示为 a(b(c,d),c(((,8))),分别写出对它进行先序、中序、后序和后序遍历的结果。
先序:
中序;
后序:
2.已知一个带权图的顶点集 V 和边集 G 分别为:
V={0,1,2,3,4,5};
E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(4,5)10},
则求出该图的最小生成树的权。
最小生成树的权;
3.假定一组记录的排序码为(46,79,56,38,40,84,50,42),则利用堆排序方法建立的初始堆为——。
4.有 7 个带权结点,其权值分别为 3,7,8,2,6,10,14,试以它们为叶子结点生成一棵哈夫曼树,求出该树的带权路径
长度、高度、双分支结点数。
带权路径长度:—— 高度:—— 双分支结点数:——。
四、阅读算法,回答问题(每小题 8 分,共 16 分)
1.VOldAC(List&L)
{
InitList(L);
InsertRear(L;25);
InsertFront(L,50);
IntaL4]={5,8,12,15,36};
for(inti=0; i<5; i++)
if (a[i]%2==0)InsertFront(L,a[i]);
elselnsertRear(L,a[i]);
}
该算法被调用执行后,得到的线性表 L 为:
2.void AG(Queue&Q)
{
InitQueue(Q);
inta[5]={6,12,5,15,8};
for(int i=0;i<5; i++)QInsert(Q,a[i]);
QInsert(Q,QDelete(Q));
QInsert(Q,20);
QInsert(Q,QDelete(Q)十 16);
while(!QueueEmpty(Q))cout<data==X)return 1; //根结点的层号为 1
//向子树中查找 x 结点
else{
int cl=NodeLevel(BT 一>left,X);
if(cl>=1)return cl+1;
//空树的层号为 0
int c2=
;
if——;
//若树中不存在 X 结点则返回 o
else return 0;
}
}
六、编写算法(8 分)
按所给函数声明编写一个算法,从表头指针为 HL 的单链表中查找出具有最大值的结点,该最大值由函数返回,若单链表为空
则中止运行。
EIemType MaxValue(LNOde*HL);
“数据结构”期末考试试题答案
6.A
散列结构(次序无先后)
一、单选题(每小题 2 分,共 12 分)
评分标准;选对者得 2 分,否则不得分。
1.B
5.B
4.D
二、填空题(每空 1 分,共 28 分)
2.B
3.C
索引结构
链接结构
1.顺序结构
2.值(或 data) 子表指针(或 sublist)
3.3 x 2.4 5/6 一*十
4.(3h 一 1)/2
5. 5
6.小于
18
大于(或大于等于)
7.向上
8.邻接矩阵
9.O(n2)
10. 1
堆顶
邻接表
边集数组(次序无先后)
O(e)
3
O(
11.13
12.同一层
13.插人
14.O(nlog2n)
选择
)
O(n2)
三、运算题(每小题 6 分,共 24 分)
1.先序:a,b,c,d,e,f,e
中序:c,b,d,a,f,8,e //2 分
后序:c,d,b,e,f,e,a //2 分
//2 分
2.最小生成树的权:31 //6 分
3.(84,79,56,42,40,46,50,38) //6 分
4.带权路径长度:131
高度:5 //2 分
双分支结点数:6 //1 分
//3 分
四、阅读算法,回答问题(每小题 8 分,共 16 分)
评分标准:每小题正确得 8 分,出现一处错误扣 4 分,两处及以上错误不得分。
1.(36,12,8,50,25,5,15)
2.5
15 8 6
20 28
五、算法填空,在画有横线的地方填写合适的内容(每小题 6 分,共 12 分)
1.feturn mid //2 分
returnBinsch(A,low,mid 一 1,K) //2 分
returnBmsch(A,mid+1,high,K) //2 分
2.NodeLevel(BT 一>right,X) //3 分
(c2>=1)returnc2 十 1 //3 分
六、编写算法(8 分)
评分标准:请参考语句后的注释,或根据情况酌情给分。
ElemType MaxValue(LNodeO* HL。)
{
if (HL==NUlL){ //2 分
cerr<<"Linked llst is empty!”<
data;
LNOde*p=HI 一>next;
while(P!:NULL){ //7 分
if(maxdata)max=p 一>data;
p=p 一>next;
}
returnmax;
}
//8 分
//3 分
//4 分
数据结构复习资料
一、填空题
1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象
以及它们之间的 关系
和运算等的学科。
2. 数据结构被形式地定义为(D, R),其中 D 是 数据元素
的有限集合,R 是 D 上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类,它们分别是 线性结构 和 非线性结构
。
5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。
6. 在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点 没有
后续结点,
其余每个结点有且只有 1 个后续结点。
7. 在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结点;叶子结点没有 后续
结点,其
余每个结点的后续结点数可以任意多个 。
8. 在图形结构中,每个结点的前驱结点数和后续结点数可以 任意多个
。
9.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有 5 种,它们分别是插入 、 删除、修改、 查找 、排序。
11. 一个算法的效率可分为 时间
效率和 空间 效率。
12. 在顺序表中插入或删除一个元素,需要平均移动 表中一半元素,具体移动的元素个数与 表长和该元素在表中的位置 有关。
13. 线性表中结点的集合是 有限
的,结点间的关系是 一对一
的。
14. 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向后移动 n-i+1 个元素。
15. 向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时,需向前移动 n-i 个元素。
16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ,因此,顺序表也称为 随机存取 的数据结构。
17. 顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。
18.在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示。
19. 在 n 个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度为 O(n)。
20. 向量、栈和队列都是 线性 结构,可以在向量的 任何
位置插入和删除元素;对于栈只能在 栈顶 插入和删除
元素;对于队列只能在 队尾
插入和 队首 删除元素。
21. 栈是一种特殊的线性表,允许插入和删除运算的一端称为 栈顶
。不允许插入和删除运算的一端称为
栈底
。
22.
队列 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。
23. 不包含任何字符(长度为 0)的串 称为空串;
由一个或多个空格(仅由空格符)组成的串
称为空白串。
24. 子串的定位运算称为串的模式匹配; 被匹配的主串
称为目标串, 子串 称为模式。
25. 假设有二维数组 A6×8,每个元素用相邻的 6 个字节存储,存储器按字节编址。已知 A 的起始存储位置(基地址)为 1000,则
数组 A 的体积(存储量)为
288 B ;末尾元素 A57 的第一个字节地址为 1282
;若按行存储时,元素 A14 的第一个字
节地址为 (8+4)×6+1000=1072
;若按列存储时,元素 A47 的第一个字节地址为 (6×7+4)×6+1000)=1276
。
26. 由3个结点所构成的二叉树有 5 种形态。
27. 一棵深度为 6 的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。
注:满二叉树没有度为 1 的结点,所以分支结点数就是二度结点数。
28. 一棵具有257个结点的完全二叉树,它的深度为 9
( 注:用 log2(n) +1= 8.xx +1=9
。
29.设一棵完全二叉树有 700 个结点,则共有 350 个叶子结点。
答:最快方法:用叶子数=[n/2]=350
30. 设一棵完全二叉树具有 1000 个结点,则此完全二叉树有 500 个叶子结点,有 499 个度为 2 的结点,有 1 个结
点只有非空左子树,有 0
个结点只有非空右子树。
答:最快方法:用叶子数=[n/2]=500 ,n2=n0-1=499。 另外,最后一结点为 2i 属于左叶子,右叶子是空的,所以有 1 个非空
左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0.
31.在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。
32. 线性有序表(a1,a2,a3,…,a256)是从小到大排列的,对一个给定的值 k,用二分法检索表中与 k 相等的元素,在查找不成
功的情况下,最多需要检索 8 次。设有 100 个结点,用二分法查找时,最大比较次数是 7
。
33. 假设在有序线性表 a[20]上进行折半查找,则比较一次查找成功的结点数为 1;比较两次查找成功的结点数为 2 ;比较
四次查找成功的结点数为 8 ;平均查找长度为 3.7 。
解:显然,平均查找长度=O(log2n)<5 次(25)。但具体是多少次,则不应当按照公式
ASL
log1
n
n
(
n
)1
2
应当用穷举法罗列:
来计算(即(21×log221)/20=4.6 次并不正确!)。因为这是在假设 n=2m-1 的情况下推导出来的公式。
全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74; ASL=74/20=3.7 !!!
34.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素 20,它将依次与表中元素
28,6,12,
20
比较大小。
35. 在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是 散列查找 。
36. 散列法存储的基本思想是由 关键字的值
决定数据的存储地址。
二、判断正误(在正确的说法后面打勾,反之打叉)
( × )1. 链表的每个结点中都恰好包含一个指针。
答:错误。链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中的结点可以含有两个指针域,分别存放指向其
直接前趋和直接后继结点的指针。
( × )2. 链表的物理存储结构具有同链表一样的顺序。错,链表的存储结构特点是无序,而链表的示意图有序。
( × )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。错,链表的结
点不会移动,只是指针内容改变。
( × )4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
错,混淆了逻辑结构与物理结构,链表也是线性表!且即使是顺序表,也能存放记录型数据。
( × )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
错,正好说反了。顺序表才适合随机存取,链表恰恰适于“顺藤摸瓜”
( × )6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
错,前一半正确,但后一半说法错误,那是链式存储的优点。顺序存储方式插入、删除运算效率较低,在表长为 n 的顺序表中,
插入和删除一个数据元素,平均需移动表长一半个数的数据元素。
( × )7. 线性表在物理存储空间中也一定是连续的。
错,线性表有两种存储方式,顺序存储和链式存储。后者不要求连续存放。
( × )8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。
错误。线性表有两种存储方式,在顺序存储时,逻辑上相邻的元素在存储的物理位置次序上也相邻。
( × )9. 顺序存储方式只能用于存储线性结构。
错误。顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如完全二叉树是属于非线性结构,但其最佳存储
方式是顺序存储方式。(后一节介绍)
( × )10. 线性表的逻辑顺序与存储顺序总是一致的。
错,理由同 7。链式存储就无需一致。
( × )11. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。
( × )12. 在表结构中最常用的是线性表,栈和队列不太常用。
错,不一定吧?调用子程序或函数常用,CPU 中也用队列。
( √ )13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。
( √ )14. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。
正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。
( × )15. 栈和链表是两种不同的数据结构。
错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项。
( × )16. 栈和队列是一种非线性数据结构。
错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。
( √ )17. 栈和队列的存储方式既可是顺序方式,也可是链接方式。
( √ )18. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间
的两端。
( × )19. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。
错,后半句不对。
( × )20. 一个栈的输入序列是 12345,则栈的输出序列不可能是 12345。
错,有可能。
( √ )21. 若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。
( × )22.二叉树中每个结点的两棵子树的高度差等于 1。
( √ )23.二叉树中每个结点的两棵子树是有序的。
( × )24.二叉树中每个结点有两棵非空子树或有两棵空子树。
( × )25.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树(若存在
的话)所有结点的关键字值。 (应当是二叉排序树的特点)
( × )26.二叉树中所有结点个数是 2k-1-1,其中 k 是树的深度。(应 2i-1)
( × )27.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。
( × )28.对于一棵非空二叉树,它的根结点作为第一层,则它的第 i 层上最多能有 2i—1 个结点。(应 2i-1)
( √ )29.用二叉链表法(link-rlink)存储包含 n 个结点的二叉树,结点的 2n 个指针区域中有 n+1 个为空指针。
( √ )30.具有 12 个结点的完全二叉树有 5 个度为 2 的结点。
三、单项选择题
( 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) 易读性、稳定性和安全性
( C )7.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:
(A)存储结构
(B)逻辑结构
(C)顺序存储结构
(D)链式存储结构
( B )8.一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是
(A)110
(B)108
(C)100
(D)120
( A )9. 在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是:
(A)
(B)
(C)
(D)
访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n)
在第 i 个结点后插入一个新结点(1≤i≤n)
删除第 i 个结点(1≤i≤n)
将 n 个结点从小到大排序
( B )10. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动 个元素
(A)8
(B)63.5
(C)63
(D)7
( A )11. 链接存储的存储结构所占存储空间:
(A) 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
(B) 只有一部分,存放结点值
(C) 只有一部分,存储表示结点间关系的指针
(D) 分两部分,一部分存放结点值,另一部分存放结点所占单元数
( B )12. 链表是一种采用
存储结构存储的线性表;
(A)顺序
(B)链式
(C)星式
(D)网状
( D )13. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址:
(A)必须是连续的
(B)部分地址必须是连续的
(C)一定是不连续的
(D)连续或不连续都可以
( B )14. 线性表L在
情况下适用于使用链式结构实现。
(A)需经常修改L中的结点值
(B)需不断对L进行删除插入
(C)L中含有大量的结点
(D)L中结点结构复杂
( B )15.栈中元素的进出原则是
A.先进先出
B.后进先出
C.栈空则进
D.栈满则出
( C )16. 若已知一个栈的入栈序列是 1,2,3,…,n,其输出序列为 p1,p2,p3,…,pn,若 p1=n,则 pi 为
A.i
B.n=i
C.n-i+1
D.不确定
( B )17. 判定一个栈 ST(最多元素为 m0)为空的条件是
A.ST->top<>0 B.ST->top=0
C.ST->top<>m0
D.ST->top=m0
( C )18. 在一个图中,所有顶点的度数之和等于图的边数的
倍。
A.1/2
B. 1
C.
2
D.
4
( B )19. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的
倍。
A.1/2
B.
1
C.
2
D.
4
( B )20. 有 8 个结点的无向图最多有
条边。
A.14
B. 28
C.
56
D. 112
( C )21. 有 8 个结点的有向完全图有
条边。
A.14
B. 28
C.
56
D. 112
( B )22.在表长为n的链表中进行线性查找,它的平均查找长度为
A. ASL=n;
C. ASL= n +1;
( A )23.折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素 58,则它将依次与表中
D. ASL≈log2(n+1)-1
B. ASL=(n+1)/2;
比
较大小,查找结果是失败。
A.20,70,30,50
B.30,88,70,50
C.20,50
D.30,88,50
( C )24.对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较
次关键字。
A.3
B.4
C.5
D. 6
( A )25. 链表适用于
查找
A.顺序
B.二分法
C.顺序,也能二分法
D.随机
《数据结构与算法》复习题
一、选择题。
1.在数据结构中,从逻辑上可以把数据结构分为 C
。
A.动态结构和静态结构
B.紧凑结构和非紧凑结构
C.线性结构和非线性结构
D.内部结构和外部结构
2.数据结构在计算机内存中的表示是指 A
。
A.数据的存储结构
B.数据结构
C.数据的逻辑结构 D.数据元素之间的关系
3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。
A.逻辑
B.存储
C.逻辑和存储
D.物理
4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C
。
A.数据的处理方法
B.数据元素的类型
C.数据元素之间的关系
D.数据的存储方法
5.在决定选取何种存储结构时,一般不考虑 A 。
A.各结点的值如何
B.结点个数的多少
C.对数据有哪些运算
D.所用的编程语言实现这种结构是否方便。
6.以下说法正确的是 D
。
A.数据项是数据的基本单位
B.数据元素是数据的最小单位
C.数据结构是带结构的数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
7.算法分析的目的是 C ,算法分析的两个主要方面是 A
。
(1)A.找出数据结构的合理性
B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进
C.分析算法的易读性和文档性
(2)A.空间复杂度和时间复杂度
B.正确性和简明性
C.可读性和文档性
D.数据复杂性和程序复杂性
8.下面程序段的时间复杂度是 O(n2)
。
s =0;
for( I =0; inext ==NULL
C.head->next ==head
D head!=NULL
15.带头结点的单链表 head 为空的判定条件是 B 。
A.head == NULL
B head->next ==NULL
C.head->next ==head
D head!=NULL
16.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点,则采用
D
存储方式最节省运算时间。
A.单链表 B.给出表头指针的单循环链表
C.双链表 D.带头结点的双循环链表
17.需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。
A.单链表 B.静态链表
C.线性链表
D.顺序存储结构