树和二叉树习题（39）
1．请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink-rlink 法存储。2．假设K1，…，Kn 是n 个关键词，试解答：
(1) 试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，
K2，…，Kn 时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。
(2) 设计一个算法，打印出该二叉查找树的嵌套括号表示结构。例如，K1=B，K2=A，K3=D，K4=C，K5=E，则用二叉查找树的插入算法建立的二叉查找树为：
该二叉查找树的嵌套括号表示结构为：B（A，D（C，E））
3．写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p 所指，其双亲结点由指针 f 所指，并假设被删除结点是其双亲结点的右孩子。用类PASCAL（或C）语言将上述算法写为过程形式。
4. 已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p 为fp 的左孩子，试编写算法，删除p 所指结点。
5．二叉排序树采用二叉链表存储。写一个算法，删除结点值是X 的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。
6. 设记录R1,R2,…,Rn 按关键字值从小到大顺序存储在数组r[1..n]中,在r[n+1]处设立一个监督哨,其关键字值为+∞; 试写一查找给定关键字k 的算法;并画出此查找过程的判定树,
求出在等概率情况下查找成功时的平均查找长度。
7．设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。
8．元素集合已存入整型数组A[1..n]中，试写出依次取A 中各值A[i](1<=i<=n)构造一棵二叉排序树T 的非递归算法：CSBT(T,A)
9．写出折半查找的算法，并要求它返回整型值i，当查找成功时，返回查找位置，查找不成功时返回0。
10．请编写算法：键树，又称数字查找树。它是一棵度为>=2 的树，树中的每个结点中不
是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键（TIRE）树T 上查找关键字等于给定值KEY 的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。
11．写出从哈希表中删除关键字为K 的一个记录的算法，设哈希函数为H，解决冲突的方法为链地址法。
12．编写一用链接表（LINKED LIST）解决冲突的哈希表插入函数。
13．在用除余法作为散列函数、线性探测解决冲突的散列表中，写一删除关键字的算法，要求将所有可以前移的元素前移去填充被删除的空位，以保证探测序列不致于断裂。
14．设排序二叉树中结点的结构为下述三个域构成: data: 给出结点数据的值；left: 给出本结点的左儿子结点的地址；right: 给出本结点的右儿子结点的地址设data 域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data 域的值小于等于x 的结点全部删除掉。
15．已知二叉树T 的结点形式为(llink, data,count,rlink,),在树中查找值为X 的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。
16．假设一棵平衡二叉树的每个结点都标明了平衡因子b,试设计一个算法，求平衡二叉树的高度。
17．设从键盘输入一个整数的序列：n,a1,a2，…，an,其中n 表示连续输入整数的个数。（1）试编写一程序按整数值建立一个二叉排序树
18.设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和
非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。
19．在单链表中，每个结点含有5 个正整型的数据元素若（最后一个结点的数据元素不满5 个，以值0 充），试编写一算法查找值为n（n>0）的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
20．编写对有序表进行顺序查找的算法，并画出对有序表进行顺序查找的判定树。假设每次查找时的给定值为随机值，又查找成功和不成功的概率也相等，试求进行每一次查找时和给定值进行比较的关键字个数的期望值。
21. 在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉，而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，
35，42．滤掉3 个元素。
22．已知二叉排序树采用二叉链表存储结构，根结点的指针为T，链结点的结构为（lchild,data,rchild），其中lchild、rchild 分别指向该结点左、右孩子的指针（当孩子结点不存在时，相应指针域为null）,data域存放结点的数据信息。请写出递归算法，从小到大输出二叉排序树中所有数据值>=x 的结点的数据。要求先找到第一个满足条件的结点后再依次输出其他满足条件的结点。
23. 已知某哈希表HT 的装填因子小于1，哈希函数H(key)为关键字的第一个字母在
字母表中的序号。
（1）处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
（2）处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找
长度的算法。注意，此算法中规定不能用公式直接求解计算。
24．有一个100*100 的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储
结构。
（1）请你设计一个哈希表
（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量存放一个非零元素的行值，列值，和元素值）作存储结构时存取元素的算法（注：此算法不需要写出，仅需说明存取的方法和所用时间）进行比较。25．将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线性探测法处理冲突（H（key）+1、H（key）+2、…、H（key）-1），假设空单元用EMPTY 表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。
26. 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列0-10 的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少？
类似本题的另外叙述有：
(1) 已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为０～１１。设计一个哈希表函数把上述关键字散到０～１１中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。
27. 已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O(m).
28．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值。
29．设计算法按中序次序依次输出各结点的值及其对应的序号。例如，下图中的二叉树的输出结果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I,9) (G,10)。
○A
○B○G
○C○D○H
○E○F○I
○
30．设计算法以输出每个结点到根结点之间的路径上的所有结点的值。
31．设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储到数组A[n]中，并将其中没有存放结点值的数组元素设置为NULL。
32．设计算法将一棵以顺序存储方式存储在数组A中的二叉树转换为二叉链表形式。33．分别设计出先序、中序和后序遍历二叉树的非递归算法。
34．分别讨论先序、中序和后序线索化二叉树中前驱和后继的求解。
35．设计一个遍历先序线索二叉树的非递归算法，要求不许用栈。
36．设计算法将值为x的结点作为右子树的（后序序列的）第一个结点的左孩子插入到后序线索二叉树中。
37．分别设计出先序、中序和后序线索化算法。
27．设计算法以实现将以二叉链表形式存储的树（森林）转换为对应的双亲表示形式。28．已知树（森林）的高度为4，所对应的二叉树的先序序列为ABCDE，请构造出所有满足这一条件的树或森林。
29．设计算法将一个以孩子链表形式表示的森林转换为二叉链表形式。
30．设计算法按先序次序输出森林中每个结点的值及其对应的层次数。
31．设计算法以求解森林的高度。
32．设计算法以输出森林中的所有叶子结点的值。
33．设计算法逐层输出森林中的所有结点的值。
34．设计算法将森林中的结点以广义表的形式输出。例如，下图中的森林的输出结果为：(A,((B,((E,(K)),F,G)),(C,(H,I)),(D,(J)))) , (L,(M,N)), (O,(P))
○A○L○O
○B○C○D○M○N○P
○E○F○G○H○I○J
○K
35．设计一个程序以对文件进行压缩，计算其压缩比例，然后对所压缩的文件进行还原。36．设计算法以产生哈夫曼树中各叶子结点的哈夫曼编码。
37. 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。
38. 以二叉链表为存储结构，编写算法对二叉树进行层次遍历（提示：应使用队列来保存各层的结点。）
39.写出二叉树的按层遍历算法
第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （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）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 、选择题（40 X 1=40分） 1 .用二维表数据来表示实体及实体之间联系的数据模型称为（ 2 .表在数据库中是一个非常重要的数据对象，它是用来（ 数据库是在计算机系统中按照一定的数据模型组织、 操作的软件系统叫 —，由计算机、操作系统、 存储和应用的 —，支持数据库各种 DBMS 、数据库、应用程序及用户等组成的一 A 、概念数据模型 B 、结构数据模型 C 物理数据模型 D 、逻辑数据模型 11.数据是信息的符号表示或称载体；信息则是数据的内涵，是数据的 12 .下列关于关系数据模型的术语中， 最接A 、 显示 B 、查询 C 、存放 D 、检索 3. 数据库创建后就可以创建表了，创建表可以用（ 等方法来创建。 A 、 企业管理器 B 、查询分析器 C 、 OSQL D 、企业管理器和 CREAT E TABL 语句 个整体叫 。（D A 、文件的集合、操作系统、文件系统 B 、 数据的集合、数据库管理系统、数据库系统 C 、命令的集合、数据库系统、软件系统 D 、 程序的集合、命令系统、数据库系统 7 .下面对于关系的叙述中，哪个是不正确的? A 、关系中的每个属性是不可分解的 C 、任意的一个二维表都是一个关系 B 、 （B ） 在关系中元组的顺序是无关紧要的 每一个关系只有一种记录类型 8 . SQL 中，下列涉及空值的操作，不正确的是（ C ) A. AGE IS NULL B. AGE IS NOT NULL C. AGE = NULL D. NOT (AGE IS NULL) 10 .在数据库技术中，实体-联系模型是一种 D )。 A 、实体--联系模型 B 、层次模型 C 、网状模型 D 、关系模型 C ）各种数据内容的。 A 、语法解释 B 、语义解释 C 、语意说明 D 、用法说明 哪一个术语所表达的概念与二维表中的 “行” 的概念 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s Data Structures and Algorithms – MidTerm Exam 1. Let ‘I’ be “push”, ‘O’ be “pop” and ‘P’ be “print” directly. To convert the infix expression a+(b*c–d)/e to its postfix through a stack, the sequence of operations are PIIPIPOIPOOIPOO (For example: (a+b) is converted to ab+ by IPIPOO.) (5 points) 2. In a binary tree of N nodes, there are N+1 NULL pointers representing children. (2 points) 3. A sorting algorithm is stable if elements with equal keys are left in the same order as they occur in the input. Which of the following algorithms is/are stable? Answer: (a) (c) (8 points) (a) insertion sort; (b) quick sort; (c) merge sort; (d) heap sort 4. The following routine removes duplicates from an array-based list A[0] … A[N-1]. LastPosition is initially N-1. for ( i = 0; i < LastPosition; i ++ ) { j = i + 1; while ( j < LastPosition ) if ( A[i] == A[j] ) Delete(j); ++; j else } (a) What is the function of Delete? (3 points) Delete A[ j ] by shifting A[ j+1 ] … A[ LastPosition-1 ] to the left. LastPosition -- . (b) T worst( N ) = O( N2 ) . (2 points) (c) Using linked list implementation, T worst( N ) =O( N2 ) . (2 points) 5. Among the given trees, d has the same inorder and preorder traversal results, and b has the same postorder and inorder traversal results. (4 points) (a) (b) (c) (d) (e) 6. Show the result of inserting { 51, 25, 36, 88, 42, 52, 15, 96, 87, 30 } into (a) an initially empty binary search tree; (b) an initially empty AVL tree; (c) an initially empty 2-3 tree. (30 points) 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 1、在数据库技术中，独立于计算机系统的模型是 C 、E-R 模型 D 、层次模型 C 。 A 、面向对象的模型 B 、关系模型 2、数据库系统的控制中枢是 _B_。A 、数据库、b 、数据库管理系统 C 、数据库管理员 D 、 数据库应用系统 3、使用 SQL 命令将学生表 STUDENT 中的学生年龄 AGE 字段的值增加 1 岁，应该使用的 命令是 __C_。 C 、UPDATE STUDENT SET AGE = AGE + 1 D 、UPDAT E STUDENT AGE WITH AGE + 1 4、 在关系数据库中，建立数据库表时，将年龄字段值限制在 12?40岁之间的这种约束属于 __B__。 A 、 视图完整性约束 B 、域完整性约束 C 、参照完整性约束 D 、实体完整性约束 5、 在 SQL 语句中，与 X BETWEEN 20 AND 30 等价的表达式是 __D_。 A 、 X>=20 AND X<30 B 、 X>20 AND X<30 C 、 X>20 AN D X<=30 D 、 X>=20 AND X<=30 6、在数据库中，概念模型是 _D_。A 、用于现实的建模，与具体的 DBMS 有关B 、用于信 息世界的建模，与具体的 DBMS 有关 C 、用于现实的建模，与具体的 DBMS 无关D 、 用于信息世界的建模，与具体的 DBMS 无关 7、数据库的并发操作可能带来的问题包括 __B_。A 非法用户的使用B 丢失更新C 数据独立 性会提高 D 增加数据冗余度 8、在关系数据库中，模式对应的是 表 C 、基本表 D 、索引 9、能实现绝 对的与平台无关性的 C 、 WebbaseAPI D 、 JDBC C 、 SQL 不能嵌入到高级语言程序中 D 、 SQL 是一种 DBMS 11、数据库系统是 由__A_组成的。A 、数据库、数据库管理系统和用户 B 、数据文件、命令文件和报表 C 、数据库文件结构和数据 D 、常量、变量和函数 12、在SQL 查询时，使用 WHER E 子句指出的是 _B_。A 、查询目标B 、查询条件 C 、查 询视图D 、查 询结果 13、在下列RDMBS 产品中，属于小型数据库系统的是 D 、Informix A 、UPDAT E SET AGE WITH AGE + 1 B 、 REPLACE AGE WITH AGE ＋1 A ___ 。A 、视图和所有基本表 B 、视图和部分基本 Web 数据库访问技术是 _D_。 A 、 ADO B 、 ActiveX 10、在下列描述中，正确的描述是 __B 合操作方式 A 、 SQL 是一种过程化语言 B 、 SQL 采用集 _A_。A 、Access B 、Oracle C 、Sybase 一、选择题 1.在逻辑上可以把数据结构分成（A） A.线性结构和非线性结构 B.动态结构和静态结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 2.单链表中各结点之间的地址（C） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 1、在数据库技术中，独立于计算机系统的模型是_C__。A、面向对象的模型B、关系模型C、E-R模型D、层次模型 2、数据库系统的控制中枢是__B_。A、数据库、b、数据库管理系统 C、数据库管理员 D、数据库应用系统 3、使用SQL命令将学生表STUDENT中的学生年龄AGE字段的值增加1岁，应该使用的命令是__C_。 A、UPDATE SET AGE WITH AGE＋1 B、REPLACE AGE WITH AGE＋1 C、UPDATE STUDENT SET AGE＝AGE＋1 D、UPDATE STUDENT AGE WITH AGE＋1 4、在关系数据库中，建立数据库表时，将年龄字段值限制在12～40岁之间的这种约束属于__B__。 A、视图完整性约束 B、域完整性约束 C、参照完整性约束 D、实体完整性约束 5、在SQL 语句中，与X BETWEEN 20 AND 30 等价的表达式是 __D_。A、X>=20 AND X<30 B、X>20 AND X<30 C、X>20 AND X<=30 D、X>=20 AND X<=30 6、在数据库中，概念模型是_D__。A、用于现实的建模，与具体的DBMS有关B、用于信息世界的建模，与具体的DBMS有关C、用于现实的建模，与具体的DBMS无关D、用于信息世界的建模，与具体的DBMS无关 7、数据库的并发操作可能带来的问题包括__B_。A非法用户的使用B丢失更新C数据独立性会提高D增加数据冗余度 8、在关系数据库中，模式对应的是__A___。A、视图和所有基本表B、视图和部分基本表C、基本表D、索引 9、能实现绝对的与平台无关性的Web数据库访问技术是_D_。A、ADO B、ActiveX C、WebbaseAPI D、JDBC 10、在下列描述中，正确的描述是__B___。A、SQL 是一种过程化语言B、SQL 采用集合操作方式 《数据结构与算法》复习题 选择题 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; i I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 一、选择题（每题1分，共20分） 1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是（ A ）阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D.数据项管理 2．数据库三级视图，反映了三种不同角度看待数据库的观点，用户眼中的数据库称为（D）。 A. 存储视图 B. 概念视图 C. 内部视图 D. 外部视图 3．数据库的概念模型独立于（A）。 A.具体的机器和DBMS B. E-R图 C. 信息世界 D. 现实世界 4．数据库中，数据的物理独立性是指（C）。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 5．关系模式的任何属性（A）。 A. 不可再分 B. 可再分 C. 命名在该关系模式中可以不惟一 D.以上都不是 6．下面的两个关系中，职工号和设备号分别为职工关系和设备关系的关键字： 职工（职工号，职工名，部门号，职务，工资） 设备（设备号，职工号，设备名，数量） 两个关系的属性中，存在一个外关键字为（ C ）。 A. 职工关系的“职工号” B. 职工关系的“设备号” C. 设备关系的“职工号” D. 设备关系的“设备号” 7．以下四个叙述中，哪一个不是对关系模式进行规X化的主要目的（ C ）。 A. 减少数据冗余 B. 解决更新异常问题 C. 加快查询速度 D. 提高存储空间效率 8．关系模式中各级X式之间的关系为（ A ）。 A. B. C. D. 9．保护数据库，防止未经授权或不合法的使用造成的数据泄漏、非法更改或破坏。这是指数据的（ A ）。 A. 安全性 B.完整性 C.并发控制 D.恢复 10．事务的原子性是指（ B ）。 A. 事务一旦提交，对数据库的改变是永久的 B. 事务中包括的所有操作要么都做，要么都不做 C. 一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D. 事务必须使数据库从一个一致性状态变到另一个一致性状态 11．下列哪些运算是关系代数的基本运算（ D ）。 A. 交、并、差 B. 投影、选取、除、联结 C. 联结、自然联结、笛卡尔乘积 D. 投影、选取、笛卡尔乘积、差运算 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data 数据结构习题 习题一 一、选择题 1、算法分析的两个主要方面是：（） A．正确性和简明性B．时间复杂度和空间复杂度 C．数据复杂性和程序复杂性D．可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．逻辑结构和存储结构 3、计算机算法具备输入、输出和（）等5个特性： A．有穷性、确定性和稳定性B．可行性、可移植性和可扩充性 C．有穷性、确定性和可行性D．易读性、稳定性和安全性 4、算法分析的目的是（）。 A．找出算法的合理性 B．研究算法的输人与输出关系 C．分析算法的有效性以求改进 D．分析算法的易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2、线性结构中元素之间存在的关系，树形结构中元素之间存在的关系， 图形结构中元素之间存在的关系。 3、________是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为________。 4、数据的________指数据元素及其关系在计算机存储器内的表示。_________是逻辑结构在计算机里的实现，也称之为映像。 5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组__________，其中每个指令表示一个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i＝0； s=0； while(s＜n） ｛ i++; s+=i; ｝ 2、写出以下算法的时间复杂度： for（i＝0; i＜m; i＋＋） for（j＝0 ; j＜t; j＋＋） c[i][j]=0； for（i=0；i＜m；i＋＋） for（j=o; j 《大学计算机基础》数据库部分选择题 1．下列四项中，不属于数据库特点的是( D ) A．数据共享 B．数据完整性 C．数据冗余较小 D．数据独立性低 2．（ C ）是长期存储在计算机内的有组织、可共享的数据集合。A．数据库管理系统 B．数据库系统 C．数据库 D．文件组织 3．数据库系统不仅包括数据库本身，还包括相应的硬件、软件和（ D ） A．数据库管理系统 B．数据库应用系统 C．相关的计算机系统 D．各类相关人员 4．在数据库系统阶段，数据是（ D ） A．有结构的 B．无结构的 C．整体无结构，记录内有结构 D．整体结构化 5．在文件系统阶段，数据（ A ） Ａ．无独立性 B．独立性差 C．具有物理独立性 D．具有逻辑独立性 6．在数据模型的三大要素中，数据的完整性约束条件规定了数据及其联系的（ A ） A．制约和存储规则 B．动态特性 C．静态特性 D．数据结构 8．数据库系统与文件系统本质的不同表现在（ A ） A．数据库中的数据是按一定的数据结构组织的 B．数据库中的数据项需指明数据类型和取值范围。 C．数据库提供了便利的存取方法。 D．数据库具有更高的数据存储量 9．DBA代表（ A ） A．数据库管理员 B．数据库管理系统 C．数据定义语言 D．数据操纵语言 10．关系数据库的数据及更新操作必须遵循（ D ）等完整性规则。A．实体完整性和参照完整性 B．参照完整性和用户自定义完整性。 C．实体完整性和用户自定义完整性。 D．实体完整性、参照完整性和用户自定义完整性 11．以下几种功能中，（ B ）是ＤＢＭＳ的控制功能。 A．数据定义 B．数据恢复 C．数据修改 D．数据查询 12数据库系统是在（ C ）的基础上发展起来的 A．操作系统 B．编译系统 C．文件系统 D．应用程序系统 13．数据的收集、整理、组织、存储、查询、维护和传送等操作，统称为（ Ｂ ） Ａ．数据操作 Ｂ．数据处理 Ｃ．数据维护 Ｄ．数据管理 14．数据库管理系统中能实现对数据库中数据的查询、插入、删除、修改等操作，这类功能称为（ C ） A．数据定义功能 B．数据管理功能 C．数据操纵功能 D．数据控制功能 15．现实世界中事物的特性在信息特性中称为（ Ｄ ） Ａ．实体 Ｂ．键 Ｃ．记录 Ｄ．属性 16．数据模型的三要素是（ D ） A．外模式、模式和内模式 B．关系模型、层次模型和网状模型C．实体、属性和联系 D．数据结构、数据操纵和完整性约束 17．ER模型是数据库设计的工具之一，用于建立数据库的（ A ）A．概念模型 B．结构模型 C．物理模型 D．文件模型 18、关系模型用（ A ）来实现关系之间的数据联系 A．外键 B．地址指针 C．主键 D．索引 19．关系模型的结构是（ B ） A．层次结构 B．二维表结构 C．网状结构 D．封装结构 20．学生社团可以接纳多名学生参加，但每个学生只能参加一个社团，数据库试题及答案
数据结构试题库答案
数据库考题及答案
经典数据结构面试题(含答案)
数据结构课后习题及解析第二章
SQL数据库选择题及答案
国家电网数据结构与算法试题
数据结构题库教材
SQL数据库选择题及答案
数据结构(C语言)【经典题库】含标准答案
数据结构例题解析(1)
数据结构相关题库及答案
数据结构经典例题
数据结构第一章课后习题与答案
数据库期末考试试题及答案
数据结构经典算法试题
数据结构题库汇总
05_数据库选择题(答案)
相关主题
文本预览