第1章 绪论
一、选择题
1.算法的计算量的大小称为计算的（ ）。
A．效率 B.复杂性 C.现实性 D.难度
2.一个算法是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 3．从逻辑上可以把数据结构分为（ ）两大类。
A．动态结构、静态结构 B．顺序结构、链式结构
C．线性结构、非线性结构 D．初等结构、构造型结构 二、判断题
1.数据元素是数据的最小单位。( )
2.数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 3.算法的优劣与算法描述语言无关，但与所用计算机有关。( )
4.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )
5.算法可以用不同的语言描述，如果用C语言来描述，则算法实际上就是程序了。( ) 6.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 三、填空
1.数据的物理结构包括数据元素的表示和 的表示。
2.对于给定的n个元素,可以构造出的四种逻辑结构有：集合、 和图状结构。 3.数据的逻辑结构是指 。
4.一个数据结构在计算机中 称为存储结构。 5.数据结构中评价算法的两个重要指标是 。
6.一个算法具有5个特性: 、有零个或多个输入、有一个或多个输出。 7.计算机执行下面的语句时，语句s的执行次数为 _______ 。 for(i=l；i s; 8.下面程序段的时间复杂度为________。(n>1) sum=1；for(i=0;sum 2.回答问题 （1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？ （2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？举例说明。 3．数据结构与数据类型有什么区别？ 4．有下列运行时间函数： （1）T1 (n)=1000; 2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1; 分别写出相应的大O表示的运算时间。 第2章 线性表 一 选择题 1.下述哪一条是顺序存储结构的优点？（ ） 1 青岛科技大学《数据结构》课程练习题及答案 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 2.下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3.线性表是具有n个（ ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5.链表不具有的特点是（ ） A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 6.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 7.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 8．线性表（a1,a2,„,an）以链式方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 9．在单链表指针为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; 10．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL 二、判断题 1.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 2.对任何数据结构链式存储结构一定优于顺序存储结构。( ) 3.集合与线性表的区别在于是否按关键字排序。( ) 4.线性表的特点是每个元素都有一个前驱和一个后继。( ) 5.循环链表不是线性表. ( ) 6.线性表就是顺序存储的表。( ) 三、填空题 1.线性表L=（a1,a2,„,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。 2.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。 3.一个具有n个结点的单链表，在已知的结点后插入一个新结点的时间复杂度为_______。 4.一个具有n个结点的单链表，在给定值的结点后插入一个新结点的时间复杂度为_____。 5.顺序存储结构是通过________表示元素之间关系的；链式存储结构是通过指针表示元素之间关系的。 6.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________ 2 青岛科技大学《数据结构》课程练习题及答案 7.在单链表L中，指针p所指结点有后继结点的条件是：__ 。 四、应用题 1．线性表有两种存储结构：一是顺序表，二是链表。试问： （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 2．线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。 3．线性表（a1，a2，„，an）用顺序映射表示时，ai和ai+1（1<=i 五、算法设计题 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 2．已知非空线性链表由list指出，链结点的构造为（data,next）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 3．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： （1）找出最小值结点，且打印该数值； （2）若该数值是奇数，则将其与直接后继结点的数值交换； （3）若该数值是偶数，则将其直接后继结点删除。 第3章 栈和队列 一、选择题 1.对于栈操作数据的原则是（ ）。 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2.一个栈的输入序列为123„n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i 3.若一个栈的输入序列为1,2,3,„,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 4.有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 5.输入序列为ABC，可以变为CBA时，经过的栈操作为（ ） A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 6.若栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 A．top:=top+1; V[top]:=x B. V[top]:=x; top:=top+1 C. top:=top-1; V[top]:=x D. V[top]:=x; top:=top-1 7.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈 3 青岛科技大学《数据结构》课程练习题及答案 顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。 A.|top[2]-top[1]|=0 B.top[2]+1=top[1] C.top[1]+top[2]=m D.top[1]=top[2] 8.一个递归算法必须包括（ ）。 A.递归部分 B.终止条件和递归部分 C.递推部分 D.终止条件和递推部分 9.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈 10.用链式方式存储的队列，在进行删除运算时（ ）。 A.仅修改头指针 B.仅修改尾指针 C.头、尾指针都要修改 D.头、尾指针可能都要修改 11.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。 A.(rear-front+m)%m B.rear-front+1 C．(front-rear+m)%m D.(rear-front)%m 12.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。 A.(rear+1)%n=front B. rear=front C．rear+1=front D. (rear-l)%n=front 13.设栈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 14．某个车站呈狭长型，宽度只能容下一辆车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入纪录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，„„，则车辆出站的顺序为（ ）。 A．1，2，3，4，5 B．1，4，3，7，6 C．1，2，4，5，7 D．1，4，3，7，2 二、判断题 1.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ ） 2.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ） 3.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。（ ） 4.栈和队列都是存取点的线性结构。（ ） 5.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。（ ） 6.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（ ） 7.循环队列也存在空间溢出问题。（ ） 三、填空题 1．_______是限定仅在表尾进行插入或删除操作的线性表。 2.一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 3.设有一个空的顺序栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，栈顶指针值是_______H。每个元素占4个字节。 4．用I表示入栈操作，O表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的I和O的操作串为_______。 5.循环队列的引入，目的是为了克服_______。 6.设循环队列用数组A[1..M]表示，队首、队尾指针分别是front和rear，判定队满的条件为_______。 7.设循环队列存放在向量sq.data[0..M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______。 4 青岛科技大学《数据结构》课程练习题及答案 四、应用题 1.有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？ 2.设一数列的输入顺序为123456，若采用栈结构，并以I和O分别表示入栈和出栈操作，试问通过入出栈操作的合法序列。 （1）能否得到输出顺序为3251的序列。 （2）能否得到输出顺序为1623的序列。 3.用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满/栈空的判断条件，并用C语言写出入栈的操作。 五 算法设计题 1.假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1）下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO （2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 2.请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH(ST,x):元素x入ST栈；POP(ST,x)：ST栈顶元素出栈，赋给变量x；Sempty(ST)：判ST栈是否为空。那么如何利用栈的运算来实现该队列的三个运算：enqueue:插入一个元素入队列； dequeue:删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释） 3.试将下列递归过程改写为非递归过程。 void test(int &sum) { int x； scanf(x)； if(x=0) sum=0 else {test(sum); sum+=x;} printf(sum)； } 第4章 串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2.若串S1=‘ABCDEFG’,S2=‘98’,S3=‘###’,S4=‘012345’,执行concat(replace (S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ） A．ABC###G0123 B．ABCD###2345 C．ABC###G1234 D．ABC###G2345 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ） A．求子串 B．联接 C．匹配 D．求串长 4．模式串t=‘abcaabbca’，该模式串的next数组的值为（ ）。 A．0 1 1 1 2 2 1 1 1 B．0 1 1 1 2 1 2 1 1 C．0 1 1 1 0 0 1 3 1 D．0 1 1 1 2 2 3 1 1 5．串的长度是指（ ） A．串中所含不同字母的个数 B．串中所含字符的个数 5 青岛科技大学《数据结构》课程练习题及答案 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 二、判断题 1．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（ ） 2．设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ） 3．串是一种数据对象和操作都特殊的线性表。（ ） 二、填空题 1．组成串的数据元素只能是________。 2．INDEX（‘DATASTRUCTURE’，‘STR’）=________。 3．设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。 4．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，称P为____。 5．串是一种特殊的线性表，其特殊性表现在____。 6. 串的两种最基本的存储方式是____。 7．两个字符串相等的充分必要条件是_______。 第5章 数组和广义表 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 2.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i 3.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。 A. 60 B. 66 C. 18000 D. 33 4.对稀疏矩阵进行压缩存储目的是（ ）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 5.广义表（（a,b,c,d））的表头是（ ）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 6.广义表（（a,b,c,d））的表尾是（ ）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 7.设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 8.下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、判断题 1.从逻辑结构上看，n维数组的每个元素均属于n个向量。（ ） 2.稀疏矩阵压缩存储后，必会失去随机存取功能。（ ） 3.数组是同类型值的集合。（ ） 4.数组可看成线性结构的一种推广，与线性表一样，可以对它进行插入，删除等操作。（ ） 5.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ ） 6 青岛科技大学《数据结构》课程练习题及答案 6.二维以上的数组其实是一种特殊的广义表。（ ） 7.若一个广义表的表头为空表，则此广义表亦为空表。（ ） 8.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（ ） 9.广义表的同级元素（直属于同一个表中的各元素）具有线性关系。（ ） 三、填空题 1.数组的存储结构采用_______存储方式。 2.二维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储) 3.己知三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为______。 4.所谓稀疏矩阵指的是_______。 5.当广义表中的每个元素都是原子时，广义表便成了_______。 第6章 树和二叉树 一、选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A．5 B．6 C．7 D．8 3.在下述结论中，正确的是（ ） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④ 4.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A．250 B． 2 C．500 D．501 6.设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 7.有关二叉树下列说法正确的是（ ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 8．二叉树的第I层上最多含有结点数为（ ） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 9.一个具有1025个结点的二叉树的高h为（ ） A．11 B．10 C．11至1025之间 D．10至1024之间 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点 A．2h B．2h-1 C．2h+1 D．h+1 11.一棵具有 n个结点的完全二叉树的树高度（深度）是（ ） A．log2n+1 B．log2n+1 C．log2n D．log2n-1 12．深度为h的满m叉树的第k层有（ ）个结点。(1= 7 青岛科技大学《数据结构》课程练习题及答案 A．2 k B．2 C．2-1 k-1k D．2-1 k-1 14. 一棵树高为K的完全二叉树至少有（ ）个结点 A．2k–1 B. 2k-1–1 C. 2k-1 D. 2k 15.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（） A．4 B．5 C．6 D．7 16．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 17．树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 D从根开始按层次遍历 18．若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。 A．前序 B．中序 C．后序 D．按层次 19．在下列存储形式中，哪一个不是树的存储形式？（ ） A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 20．二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、 E B、 F C、 G D、 H 21．一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ） A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树 22.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点 23. 引入二叉线索树的目的是（ ） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 24．n个结点的线索二叉树上含有的线索数为（ ） A．2n B．n－l C．n＋l D．n 25．下述编码中哪一个不是前缀码（ ）。 A．（00，01，10，11）B．（0，1，00，11）C．（0，10，110，111）D．（1，01，000，001） 二、判断题 1.二叉树是度为2的有序树。 2.完全二叉树一定存在度为1的结点。 3.二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。 4．由一棵二叉树的前序序列和后序序列可以唯一确定它。 5．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 6.一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i 8 青岛科技大学《数据结构》课程练习题及答案 情形. 9．树形结构中元素之间存在一个对多个的关系。 10．在二叉树中插入结点，则此二叉树便不再是二叉树了。 11．树与二叉树是两种不同的树型结构。 12.非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子 13．哈夫曼树的结点个数不能是偶数。 14．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。 15．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 三、填空题 1．二叉树由根结点，左子树，___三个基本单元组成。 2．在二叉树中，指针p所指结点为叶子结点的条件是______。 3．深度为k的完全二叉树至少有______个结点，至多有2-1个结点。 4．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。 5．一棵有n个结点的满二叉树有__ _个度为1的结点。 6．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。 7．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______。 8．高度为8的完全二叉树至少有______个叶子结点。 9．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。 10．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。 11．利用树的孩子兄弟表示法存储，可以将一棵树转换为______。 12．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的______序列中的最后一个结点。 13.在一棵存储结构为三叉链表的二叉树中，若有一个结点是它的双亲的左子女，且它的双亲有右子女，则这个结点在后序遍历中的后继结点是______。 14．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。 15．有一份电文使用 6个字符:a,b,c,d,e,f,它们的出现频率依次为2,3,4,7,8,9，字符c的编码是_(2)__。 四、应用题 1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。 2．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求： 1）各层的结点的数目是多少？ 2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i个孩子结点（若存在）的编号是多少？ 4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。 3．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 4．若一棵树中有度数为1至m的各种结点数为n1,n2,„,nm(nm表示度数为m的结点个数)请推导出该树有多少个叶子结点n0的公式。 5．一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。 先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G k 9 青岛科技大学《数据结构》课程练习题及答案 后序序列 ：_ E F D B _ J I H _ A 6．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。 7．设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若 T中有6个叶结点，试问： （1）T树的最大深度Kmax=?最小可能深度Kmin=? （2）T树有多少非叶结点？ (3) 若叶结点的权值分别为1,2,3,4,5,6。请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。 第7章 图 一、选择题 1．图中有关路径的定义是（ ）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 3．一个n个顶点的连通无向图，其边的个数至少为（ ）。 A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 5．n个结点的完全有向图含有边的数目（ ）。 A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l） 6．下列哪一种图的邻接矩阵是对称矩阵？（ ） A．有向图 B．无向图 C．AOV网 D．AOE网 7. 下列说法不正确的是（ ）。 A． 图的遍历是从给定的源点出发每一个顶点仅被访问一次 B． 遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 9．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f), (f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 9．下面哪一方法可以判断出一个有向图是否有环（回路）：( ) A．广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 10. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 11．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 10 青岛科技大学《数据结构》课程练习题及答案 A．G中有弧 A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 14. 关键路径是事件结点网络中（ ）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 15. 下面关于求关键路径的说法不正确的是（ ）。 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D．关键活动一定位于关键路径上 16．下列关于AOE网的叙述中，不正确的是（ ）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 二、判断题 1. 图中的顶点就是指数据结构中的数据元素。（ ） 2．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ） 3. 有e条边的无向图，在邻接表中有e个结点。（ ） 4. 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（ ） 5. 无向图的邻接矩阵可用一维数组存储。（ ） 6．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（ ） 7．有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（ ） 8．无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 9．一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ） 10. 广度遍历生成树描述了从起点到各顶点的最短路径。（ ） 11．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ） 12. 最小生成树问题是构造连通网的最小代价生成树。（ ） 13. 在图G的最小生成树G1中，可能会有某条边的权值超过未选边的权值。（ ） 14．AOV网的含义是以边表示活动的网。（ ） 15．在AOE图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。（ ） 三、填空题 1. 判断一个无向图是一棵树的条件是______。 2．有向图G的强连通分量是指______。 3．一个连通图的______是一个极小连通子图。 4．G是一个非连通无向图，共有2边，则该图至少有______个顶点。 5．在有n个顶点的有向图中，每个顶点的度最大可达______。 6．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。 7．无向图G的邻接表表示中，每个顶点邻接表中所含的结点数等于该顶点的______。 8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)} 11 青岛科技大学《数据结构》课程练习题及答案 现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。 9. 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。 10．构造连通网最小生成树的两个典型算法是______。 11. kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。 12．对于含N个顶点E条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为______。 13. 求从某源点到其余各顶点的Dijkstra算法在图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms,则在图的顶点数为40，计算时间约为______ms。 四、应用题 1．用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否有关？ 2．请回答下列关于图(Graph)的一些问题： （1）．有n个顶点的有向强连通图最多有多少条边?最少有多少条边? （2）．表示有1000个顶点、l000条边的有向图的邻接矩阵有多少个矩阵元素？是否稀 疏矩阵？ （3）．对于一个有向图，不用拓扑排序，如何判断图中是否存在环？ 3．解答问题。设有数据逻辑结构为： B = (K, R), K = {k1, k2, „, k9} R={ （1）．画出这个逻辑结构的图示。 （2）．相对于关系R, 指出所有的开始接点和终端结点。 （3）．分别对关系R中的开始结点，举出一个拓扑序列的例子。 （4）．分别画出该逻辑结构的正向邻接表和逆向邻接表。 4．某田径赛中各选手的参赛项目表如下: 姓名 参 赛 项 ZHAO A B E QIAN C D SHUN C E F LI D F A ZHOU B F 设项目A ,B ,„，F各表示一数据元素,若两项目不能同时举行,则将其连线(约束条件). （1）．根据此表及约束条件画出相应的图状结构模型,并画出此图的邻接表结构; （2）．写出从元素A出发按“广度优先搜索”算法遍历此图的元素序列. 5．已知世界六大城市为:北京(PE)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) PE N PA L PE 109 82 81 N 109 58 55 PA 82 58 3 L 81 55 3 T 21 108 97 95 M 124 32 92 12 青岛科技大学《数据结构》课程练习题及答案 T M 21 124 108 32 97 92 95 113 113 （1）．画出这六大城市的交通网络图; （2）．画出该图的邻接表表示法; （3）．画出该图按权值递增的顺序来构造的最小(代价)生成树. 6．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 V2 V3 V4 V5 V6 V7 V8 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 V10 0 0 0 0 0 0 0 0 0 0 当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。 第8章 查找 一、选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2.对线性表进行折半查找时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序 3．若要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分块查找 B. 顺序查找 C. 折半查找 D. 基于属性 4．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 5.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 6. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) A．8 B．3 C．5 D．9 7. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行多少次探测？( ) 13 青岛科技大学《数据结构》课程练习题及答案 A．k-1次 B. k次 C. k+1次 D. k（k+1）/2次 8. 哈希表的地址区间为0-17,哈希函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ ）。 A． 8 B. 9 C. 10 D. 11 二、判断题 1．哈希函数的选取平方取中法最好。( ) 2. 顺序查找法适用于存储结构为顺序或链接存储的线性表。( ) 3. 折半查找法的查找速度一定比顺序查找法快 。( ) 4. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。( ) 5．最优二叉树是平衡二叉树。( ) 6.虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。( ) 7.二叉排序树删除一个结点后，仍是二叉排序树。( ) 三、填空题 1.在n个元素的顺序表，使用监视哨顺序查找，若查找失败，则比较关键字的次数为__ __。 2.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。 3.在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________ 4.平衡二叉树又称__________。 5.平衡因子的定义是__________。 6.__________法构造的哈希函数肯定不会发生冲突。 7.动态查找表和静态查找表的重要区别在于前者包含有____________运算，而后者不包含这两种运算。 四、应用题 1.在采用线性探测法处理冲突的哈希表中，所有同义词在表中是否一定相邻？ 2.设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,„,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 3.设一个哈希表含hashsize=13个表项，其下标从0到12，采用线性探查法解决冲突。请按以下要求，将关键字{10,100,32,45,58,126,3,29,200,400,0}散列到表中。 （1）哈希函数采用除留余数法，用% hashsize（取余运算）将各关键码映像到表中，请指出每一个产生冲突的关键字可能产生多少次冲突。 （2）哈希函数采用先将关键字各位数字折叠相加，再用% hashsize将相加的结果映像到表中的办法。请指出每一个产生冲突的关键字码可能产生多少次冲突。 第9章 排序 一、选择题 1．下列排序方法中，哪一个是稳定的排序方法？（ ） A．简单选择排序 B．折半插入排序 C．希尔排序 D．快速排序 2．若要求尽可能快地对序列进行稳定的排序，则应选（ ）。 A．快速排序 B．归并排序 C．冒泡排序 D．插入排序 3．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。 A．直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序 4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4）15 21 25 47 84 14 青岛科技大学《数据结构》课程练习题及答案 则采用的排序是 ( )。A.选择 B.冒泡 C.快速 D. 插入 5．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B.shell排序 C.堆排序 D.冒泡排序 6．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A． 冒泡 B. 希尔 C. 快速 D.堆 7.就平均性能而言，目前最好的内排序方法是( )排序法。 A.冒泡 B. 希尔插入 C.交换 D. 快速 8．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9.下列排序算法中，占用辅助空间最多的是：( )。 A.归并排序 B.快速排序 C.希尔排序 D.堆排序 10.在排序算法中，每次从未排序的记录中挑出最小（或最大）关键字字的记录，加入到已排序记录的末尾，该排序方法是（ ）。 A.选择 B.冒泡 C.插入 D.堆 11．用直接插入排序方法对下面四个序列进行排序（升序），元素比较次数最少的是（ ）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40 12.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( ) 。 A.l B.4 C.3 D.2 13．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。 A．n/2 B．n/2-1 C．1 D．n/2 +2 14.以下序列不是堆的是( )。 A. (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10) C. (10,20,40,60,66,77,80,82,85,98,100) D. (100,85,40,77,80,60,66,98,82,10,20) 二、判断题： 1．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 2．简单选择排序算法在最好情况下的时间复杂度为O（n）。（ ） 3．在待排数据基本有序的情况下，快速排序效果最好。（ ） 4．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（ ） 5．堆肯定是一棵平衡二叉树。（ ） 6．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ） 7．归并排序辅助存储空间为O（1）。（ ） 8．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （ ） 9．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（ ） 10．在任何情况下，归并排序都比简单插入排序快。（ ） 三、填空题 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记 15 青岛科技大学《数据结构》课程练习题及答案 录的_____。 5．直接插入排序用监视哨的作用是_______。 6．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 9．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。 四、应用题 1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。 2．在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？ 3．在堆排序、快速排序和合并排序中： (1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法？ (2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 4．设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k，最好采用什么排序方法？为什么？如果有这样一个序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，对于该例使用所选择的方法实现时，共执行多少次比较？ 5．奇偶交换排序如下所述：对于初始序列A[1]，A[2],„,A[n],第一趟对所有奇数i（1<=i 1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。 16 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- ovod.cn 版权所有 湘ICP备2023023988号-4
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务