《基本数据结构及其运算习题.pdf》由会员分享，可在线阅读，更多相关《基本数据结构及其运算习题.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 基本数据结构及其运算 一、单项选择题 1数据的基本单位是(B )A数据 B数据元素 C数据项 D数据结构 2在数据结构中，构成数据元素的最小单位称为（D）A字符 B关键字 C数据元素 D数据项 3数据在计算机内的存储形式称为数据的（D ）A算法描述 B数据类型 C逻辑结构 D物理结构 4数据的逻辑结构可分为（C）A顺序结构和链式结构 B 简单结构和复杂结构 C线性结构和非线性结构 D 动态结构和静态结构 5顺序表中的每个元素占 m 个字节，第一个元素的存储地址为 LOC(1)，则任意 1 个元素 i 的地址为(B )ALOC(1)+i*m BLOC(1)+(i-1)*m CLCO(1)
2、+(i+1)*m D(i-1)*m 6线性表若采用链表存储，其（D）A所有结点的地址必须是连续的 B部分结点的地址必须是连续的 C所有结点的地址一定不连续 D所有结点的地址连续、不连续都可以 7线性表在采用链式存储时，其地址（C ）A必须是连续的 B一定是不连续的 C连续不连续都可以 D部分是连续的 8下列不属于线性结构的是(C )。A单链表 B队列 C二叉树 D数组 9链表不具有的特点是(A )A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表的长度成正比 10数据结构反映了数据元素之间的结构关系，链表是一种(D )。A顺序存储线性表 B非顺序存储非线
3、性表 C顺序存储非线性表 D非顺序存储线性表 11在单链表表示的线性表中，可以从(A )。A第一个结点访问到所有结点 B某个结点访问到所有结点 C某个结点访问到该结点的所有前趋结点 D最后一个结点访问到所有结点 12在一个单链表中，已知指针 q 所指向的结点是指针 p 所指向的结点的前驱结点，若在指针 q 和 p 所指向的两个结点之间插入指针 s 指向的结点，则执行(C)。As-link=p-link;p-link=s;Bp-link=s-link;s-link=p;Cq-link=s;s-link=p;Dp-link=s;s-link=q;13长度为 n 的顺序存储的线性表，设在任何位置上删
4、除一个元素的概率相等，则删除一个元素时平均要移动的元素个数是（A）A(n-1)/2 Bn/2 Cn-1 Dn+1 14 设长度大于1带头结点的循环单链表head的尾结点由rear指向，则 head 和 rear 满足关系（B ）Arear-link=NULL Brear=head-link C.rear-link=head Drear=head 15在链式存储的线性表中，插入一个元素时（D）A需要移动元素和修改指针 B不需要移动元素和修改指针 C需要移动元素，但不需要修改指针 D不需要移动元素，但需要修改指针 16设循环队列中有 m 个单元，队列满的条件是(A )Arear=front B(r
5、ear+1)%m=front Crear%m=front Drear+1=front 17栈和队列都是(C )。A顺序存储的线性结构 B链式存储的线性结构 C限定存取点的线性结构 D限定存取点的非线性结构 18栈和队列(C )A的共同点都是先进后出 B的共同点都是先进先出 C的共同点是只允许在端点处插入和删除元素 D没有共同点 19若一个栈的输入序列是 1，2，3，n，输出序列的第一个元素是 n，则第 i 个输出元素是（B）An-i Bn-i+1 Ci Dn-i-1 20设栈初始为空，输入序列为：a，b，c，d。经过入栈、入栈、出栈、入栈、出栈、入栈操作之后，栈中的元素(从栈底到栈顶)依次为(
6、A )Aa，d Ba,c Cb，c Dd,a 21设栈初始为空，输入序列为：a,b,c。经过入栈、出栈、入栈、入栈、出栈操作之后，从栈中输出的序列为(b )Aa,b Bb,a Ca,c Db,c 22栈结构通常采用的两种存储结构是(A )A顺序存储结构和链表存储结构 B链表存储结构和数组 C线性存储结构和非线性存储结构 D 散列方式和索引方式 23有 6 个元素按 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列?(C )A5，4，3，6，1，2 B4，5，3，1，2，6 C3，4，6，5，2，1 D2，3，4，1，5，6 24设栈 S 最多能容纳 4 个元素，现有 6 个元
7、素按 a,b,c,d,e,f顺序进栈，入栈、出栈操作可随时进行，可能的出栈序列是（C）Ae,b,c,d,a,f Bb,c,e,f,a,d Cc,b,e,d,a,f Da,d,f,e,b,c 25一个队列的入队的序列是 1，2，3，4，在入队操作的同时，随时有出队的操作，则能够实现的输出序列是（A）A1234 B1432 C3241 D4321 26设队列初始为空，入队序列为：a，b，c，d。经过入队、入队、出队、出队、入队、入队操作之后，队列中从队首至队尾的元素依次为（A ）Ac，d Bb，a Cc，b Da，b 27二维数组 A1020采用行序为主方式存储，每个元素占一个存储单元，并且 A0
8、0的存储地址是 200，则 A6l2的地址是(C )A315 B326 C332 D338 28 稀疏矩阵一般的压缩存储方法有两种，即(C )。A 二维数组和三维数组 B 三元组和散列 C 三元组和十字链表 D 散列和十字链表 29.若完全二叉树的某结点无左孩子结点，则(A )A它一定是叶子结点 B它可能有右孩子结点 C它一定是在最低层 D以上说法均不对 30设二叉树共有 n 个叶子结点，所有非叶子结点都有左右子树，则此二叉树共有的结点数是(D )A2(n-1)B2n+1 C2n D2n-1 31.二叉树与树是两个不同的概念，二叉树的根结点有(A )。A0 个或 1 个 B 0 个或多个 C且
9、仅有一个 D一个或一个以上 32深度为 5 的二叉树至多有(B )个结点。A30 B31 C32 D 63 33 一棵深度为 k(k1)的完全二叉树，其结点个数至多为（2的 k 次方-1 ）A2k-1-1 B2k-1 C2k-1 D 2k 34深度为 5 的二叉树的结点最多有（C ）A10 个 B16 个 C31 个 D32 个 35具有 n 个结点的完全二叉树的深度为(D)Alog2n Blog2n Clog2n+1 Dlog2n+1 36设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数至少为(B )。A 2h B 2h-1 C2h+1 D h+1 37
10、二叉树的第 i（i1）层上结点个数至多有（2 的 i-1次方 ）A2i-1-1 B2i-1 C2i-1 D2i 38 具有 65 个结点的完全二叉树其深度为(C )(根的结点号为 1)A8 B7 C6 D5 39已知某二叉树的后序遍历序列是 d a b e c，中序遍历序列是 d e b a c，则它的前序遍历序列是(C )A a c b e d Bd e c a b C c e d b a Dd e a b c 40在顺序表(3，6，8，10，12，15，16，21，25，30)中，用二分法查找值 11，所需比较次数为(C )A 2 B3 C 4 D5 41树是由一个或多个结点组成的有序集合
11、，它有(A )称为根(root)的结点。A0 个或 1 个 B0 个或多个 C且仅有 1 个 D1 个或1 个以上 42对长度为 n 的顺序表进行顺序查找，在等概率查找情况下，查找成功的平均查找长度为（B ）A(n-1)2 Bn2 C(n+1)2 Dn 43散列函数处理冲突中的开地址法包含(B )A拉链法和线性探测法 B线性探测法和双重散列法 C拉链法和双重散列法 D拉链法和伪随机数法 二、填空题 1从逻辑上抽象地反映_数据元素_之间的结构关系称为数据的逻辑结构。2 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的结构称为_数据的存储结构（也称数据的物理结构）_。3从逻辑上抽象地反映数据元
12、素之间的结构关系，称之为数据的_数据的逻辑结构_。4顺序存储结构是把_相邻_的数据元素存储在物理上相邻的存储单元中。5在一个长度为 n 的顺序表中的第 i(1in)个元素之前插入一个元素时，需向后移动_n-i+1_个元素。6在线性表的顺序存储结构中，设第一个元素的存储地址是1000，每个元素的长度为 4，则第 10 个元素的地址是_1000+（10-1）*4=1036_。7在线性表中，元素之间存在着线性逻辑关系，元素 ai-1 被称为元素 ai 的_前件（前驱）_。8设二维数组 A，行下标的范围是 1 到 6，列下标的范围是0 到 9，每个元素占有 8 个字节。数组 A 所需的存储空间大小为_
13、480_个字节。9采用 FIFO(先进先出)的线性表称为_队列_。10不含任何数据元素的栈称为_空栈_。11栈的特点是_先进后出，后进先出_，队列的特点是_先进先出，后进后出_。12设有二维数组 A1020，其每个元素占两个字节，数组以列序为主序存储，第一个元素的存储地址为 100，那么元素 A77的存储地址为_。13二维数组 A810采用列序为主顺序存贮，每个数组元素占 2 个存储单元，且第 1 行，第 1 列的数据元素 a00的存储地址是 500，则 a68的存贮地址是_ _。14数组 A 中的每个元素占 4 个字节，行下标 i 从 0 到 8，列下标 j 从 1 到 10，存储该数组至少
14、需要_个字节。15设一棵二叉树有 10 个度为 2 的结点，则该二叉树的叶子结点的个数为_11_。16具有 n(n2)个结点的二叉树采用二叉链表进行存储，在这 2n 个指针域中共有_个指针域是空的。17在一棵二叉树中，设度为 0 的结点个数为 n0，度为 2 的结 点 个 数 为n2，则n0与n2的 关 系 为n0=_n2+1_。三、简答题 1试举例说明数据的顺序存储结构。2分别画出 3 个结点的二叉树的所有不同形态。3一棵二叉树的先序、中序遍历序列分别如下，请构造出该二叉树。先序ABDGHECFIJ 中序GDHBEACIJF 4有一棵二叉树如下图所示，试写出该二叉树的先序遍历和后序遍历序列。
15、先序:ABDECFGH 后序：EBDHGFCA 5有一棵二叉树如下图所示，试写出该二叉树的先序、中序和后序遍历序列。先序：AEDCJBFGHI 中序：BCJDEAHGIF 后序：BCJDEHIGFA 6已知一棵树如右图所示，请回答下列问题：（1）哪些是叶子结点？d，l，f，j，k （2）哪些是结点 f 的兄弟？g，h （3）树的深度是多少？5 （4）树的度数是多少？3（5）将该树转化为二叉树。7现有一个 12 个元素的有序表，关键字就是数据元素的值；4,7,10,12,15,17,20,24,26,2930,32 试写出用二分查找方法查找关键字 K=12 的元素的查找过程。8已知散列函数为 H
16、(k)=k mod 12，键值序列为 25，37，52，43，84，99，120，15，26，11，70，82，处理冲突方法为线性探测法，散列表长为 12，试画出散列表。四、完成下列算法。1设 r 是一个整型数组，下面的算法是将 r 中所有负数都移到 r 的前部，而所有正数移到 r 的后部。试将算法补充完整，以实现该算法的预定功能。#define n 100 int rn+1;void rsort()int i，j;i=1；j=n；while(ij)while(ij&ri0)(1)i+;while i0 (2)j-;r0=ri;ri=rj;rj=r0;i+;j-(3);(1)_(2)_(3)_
17、 2 已 知 在 一 维 数 组 Am+n 中 依 次 存 放 的 元 素 为：（a1,a2,am,b1,b2,bn）。下面的算法是将它们的位置互换，即互换成：（b1,b2,bn,a1,a2,am）。试在算法中的空格处填上正确的内容，以实现算法的功能。#define T 1000 int a T;int invert(int m,int n)int i,x;for(i=0;i=(m+n-1)/2;i+)x=ai ai=am+n-1-i (1)am+n-1-i=x;for(i=0;i=(n-1)/2 (2);i+)x=ai;ai=an-1-i;an-1-i=x;for(i=n(3);ilink;
18、q-link=p;p=(2);q=r;head-link=NULL;head=(3);五、算法设计题 1假设线性表用长度为 m 的一维数组 A 来存储，线性表的长度为 n,nm,其中的元素按值非递减有序排列。编写一个算法，插入一个元素 x 后，该线性表仍按非递减有序排列。2有两个一维数组 a(有 m 个元素)和 b(有 n 个元素)，其元素均按从小到大的升序排列。试编写一个算法，将它们合并成一个一维数组 c，要求 c 中的元素也是按从小到大的升序排列。3试编写计算一个不带表头结点的单链表长度的算法。4 在链式队列中，编写出计算该链式队列中结点个数的算法。（要求给出结点的结构）5对一个已建立好的单链表（表头指针为 head），编写一算法计算该链表中的结点个数。（要求给出结点的结构描述）6编写一个算法，将一维数组 a(有 n 个元素，且任何元素均不为零)分拆成两个数组b和c,使a中大于零的元素存放在b 中，小于零的元素存放在 c 中。7设单链表 head 的结点结构为 typedef struct snode int data；struct snode *link；NODE；编写算法，判断该链表的元素值是否是递增的,是递增返回“1”，否则返回“0”。