中南大学现代远程教育课程考试复习题及参考答案
数据结构
一、判断题：
1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 [ ] 2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 [ ] 3．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 [ ] 4．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。 [ ] 5．一个广义表的表尾总是一个广义表。 [ ] 6．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。 [ ] 7．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。 [ ] 8．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。 [ ] 9．直接选择排序是一种稳定的排序方法。 [ ] 10．30、闭散列法通常比开散列法时间效率更高。 [ ] 11．有n个结点的不同的二叉树有n!棵。 [ ] 12．直接选择排序是一种不稳定的排序方法。 [ ] 13．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。 [ ] 14．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。 [ ] 15．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。 [ ] 16．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。在设计再散列函数时，要求计算出的值与表的大小m互质。 [ ] 17．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有n k个，则有n0=n k+1。 [ ] 18．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。 [ ] 19．如果两个串含有相同的字符，则这两个串相等。 [ ] 20．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。 [ ] 21．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。 [ ] 22．在顺序表中取出第i个元素所花费的时间与i成正比。 [ ] 23．在栈满情况下不能作进栈运算，否则产生“上溢”。 [ ] 24．二路归并排序的核心操作是将两个有序序列归并为一个有序序列。 [ ] 25．对任意一个图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点. [ ] 26．二叉排序树或者是一棵空二叉树，或者不是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值;若它的右子树非空，则根结点的值小于其右孩子的值。 [ ] 27．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。 [ ] 28．一个有向图的邻接表和逆邻接表中表结点的个数一定相等。 [ ] 29．数据的基本单位是数据项。
30．带权的无向连通图的最小生成树是唯一的。 [ ] 31．数组元素之间的关系，既不是线性的，也不是树形的。 [ ] 32．对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。 [ ] 33．用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 [ ] 34．在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。 [ ] 35．线性表采用顺序存储表示时，必须占用一片连续的存储单元。 [ ] 36．由树转化成二叉树，其根的右子女指针总是空的。 [ ] 37．树形选择排序是一种不稳定的排序方法。 [ ] 38．中序遍历二叉树是一个有序序列。 [ ]
39．装载因子是散列表的一个重要参数，它反映了散列表的装满程度。 [ ]
二、选择题：
1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为 [ ]
A. O(n)
B. O(n／2)
C. O(1)
D. O(n2)
2.带头结点的单链表first为空的判定条件是： [ ]
A. first==NULL
B. first一>1ink＝＝NULL
C. first一>link==first
D. first!＝NUlL
3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为 [ ]
A. n-2
B. n-l
C. n
D. n+1
4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为对
应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的 [ ]，在被调用程序中可直接操纵实际参数。
A.空间
B.副本
C.返回地址
D.地址
5.在一棵树中，[ ]没有前驱结点。
A.分支结点
B.叶结点
C.树根结点
D.空结点
6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加 [ ]
A. 2
B. 1
C. 0
D. -1
7.对于长度为9的有序顺序表,若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为[ ]
的值除以9。
A. 20
B. 18
C. 25
D. 22
8.在有向图中每个顶点的度等于该顶点的 [ ]
A.入度
B.出度
C.入度与出度之和
D.入度与出度之差
9.在基于排序码比较的排序算法中，[ ]算法的最坏情况下的时间复杂度不高于O(n1og2n)。
A.起泡排序
B.希尔排序
C.归并排序
D.快速排序
10.当α的值较小时，散列存储通常比其他存储方式具有[ ]的查找速度。
A.较慢
B.较快
C.相同
D.不清楚
11.设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项
的平均探查次数不超过1.5，则散列表项应能够至少容纳[ ]个表项。
(设搜索成功的平均搜索长度为ASL＝{1+l／(1一α)}／2，其中α为装填因子)
A. 400
B. 526
C. 624
D. 676
12.堆是一个键值序列{k1,k2,…..k n},对I=1,2,….|_n/2_|,满足[ ]
A. ki≤k2i≤k2i+1
B. k i C. k i≤k2i且k i≤k2i+1(2i+1≤n) D. k i≤k2i或k i≤k2i+1(2i+1≤n) 13.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上 [ ] A.操作的有限集合 B.映象的有限集合 C.类型的有限集合 D.关系的有限集合 14.在长度为n 的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为 [ ] A. n-i+1 B. I C. i+1 D. n-i 15.若不带头结点的单链表的头指针为 head，则该链表为空的判定条件是 [ ] A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 16.引起循环队列队头位置发生变化的操作是 [ ] A.出队 B.入队 C.取队头元素 D.取队尾元素 17.若进栈序列为1，2，3，4，5，6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是 [ ] A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 18.字符串通常采用的两种存储方式是 [ ] A.散列存储和索引存储 B.索引存储和链式存储 C.顺序存储和链式存储 D.散列存储和顺序存储 19.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移 次数为 [ ] A. m B. n-m C. n-m+1 D. n 20.二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个 元素的地址为150，则元素A［9］［7］的地址为 [ ] A. 429 B. 432 C. 435 D. 438 21.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是 [ ] A. (e,f) B. ((e,f)) C. (f) D. ( ) 22.下列图示的顺序存储结构表示的二叉树是 [ ] 23. n个顶点的强连通图中至少含有 [ ] A. n-1条有向边 B. n条有向边 C. n(n-1)/2条有向边 D. n(n-1)条有向边 24.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 [ ] A.(19，23，56，34，78，67，88，92) B.23，56，78，66，88，92，19，34) C.(19，23，34，56，67，78，88，92) D.(19，23，67，56，34，78，92，88) 25.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为 [ ] A. 4 B. 5 C. 8 D. 9 26.由同一关键字集合构造的各棵二叉排序树 [ ] A.其形态不一定相同，但平均查找长度相同 B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 27.ISAM文件和VSAM文件的区别之一是[ ] A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 28.下列描述中正确的是 [ ] A.线性表的逻辑顺序与存储顺序总是一致的 B.每种数据结构都具备三个基本运算：插入、删除和查找 C.数据结构实质上包括逻辑结构和存储结构两方面的内容 D.选择合适的数据结构是解决应用问题的关键步骤 29.下面程序段的时间复杂度是 [ ] I=s=0 While(s {I++; s+=I; } A．O(1) B. O(n) C.O(log2n) D.O(n^2) 30.对于顺序表来说，访问任一节点的时间复杂度是 [ ] A．O(1) B.O(n) C.O(log2n) D.O(n^2) 31.在具有n个节点的双链表中做插入、删除运算，平均时间复杂度为 [ ] A．O(1) B.O(n) C.O(log2n) D.O(n^2) 32.经过下列运算后，QueueFront(Q)的值是 [ ] InitQueue(Q);EnQueue(Q,a);EnQueue(Q,a);DeQueue(Q,x); A. a B.b C.1 D.2 33.一个栈的入栈序列是a,b,c，则栈的不可能输出序列是 [ ] A. acb B.abc C.bca D.cab 34.循环队列是空队列的条件是 [ ] A．Q->rear==Q->front B.(Q->rear+1)%maxsize==Q->front C.Q->rear==0 D.Q->front==0 35.设s3="I AM",s4="A TERCHER"。则strcmp(s3,s4)=[ ] A.0 B.小于0 C.大于0 D.不确定 36.一维数组的元素起始地址loc[6]=1000，元素长度为4，则loc[8]为 [ ] A.1000 B.1004 C.1008 D.8 37.广义表（（a,b）,c,d）的表尾是 [ ] A．a B.b C.(a,b) D.(c,d) 38.对于二叉树来说，第I层上至多有____个节点 [ ] A.2i B. 2i -1 C.2i-1 D.2i-1-1 39.某二叉树的前序遍历序列为ABDGCEFH,中序遍历序列为DGBAECHF，则后序遍历序列为 [ ] A.BDGCEFHA B.GDBECFHA C.BDGAECHF D.GDBEHFCA 40.M叉树中，度为0的节点数称为 [ ] A.根 B.叶 C.祖先 D.子孙 41.已知一个图如下所示，若从顶点a出发按宽度搜索法进行遍历，则可能得到的一种顶点序列为[ ] 42.堆的形状是一棵 [ ] A.二叉排序树 B.满二叉树 C.完全二义树 D.平衡二叉树 43.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一 端的方法，称为 [ ] A.希尔排序 B.归并排序 C.插入排序 D.选择排序 44.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 [ ] A.n B.n/2 C.(n+1)/2 D.(n-1)/2 45.散列查找是由键值______确定散列表中的位置，进行存储或查找 [ ] A.散列函数值 B.本身 C.平方 D.相反数 46.顺序文件的缺点是 [ ] A.不利于修改 B.读取速度慢 C.只能写不能读 D.写文件慢 47.索引文件的检索方式是直接存取或按_____存取 [ ] A.随机存取 B.关键字 C.间接 D.散列 48.若需要利用形参直接访问实参，则应把形参变量参数说明为 [ ] A.指针 B.引用 C.传值 D.常值 49.以下说法错误的是 [ ] A.抽象数据类型具有封装性 D.抽象数据类型具有信息隐蔽性 C.使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作 D.抽象数据类型的一个特点是使用与实现分离 50.设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存 放于B[0]中，那么第i行的对角元素A[I][i]存放于B中( ) 处。 [ ] A.(i+3)*i／2 D.(i+1)*i／2 C.(2n—i+1)*i／2 D.n(2n—i一1)*i／2 51.已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为 [ ] A．O(1) B．O(m) C．O(n) D．O(m+n) 52.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为 [ ] A．front==rear B，front! =NULL C．rear! =NULL D．front＝＝NULL 53.设有一个递归算法如下 int fact(intn){／／n大于等于0 if(n<=0)return 1； else return n*fact(n一)； } 则计算fact(n)需要调用该函数的次数为 [ ] A．n B．n+1 C.n+2 D．n-l 54.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于[ ]。 A．2h—1 B．2h十1 C．2h一1 D．2h 55.一棵树的广义表表示为a(b，c(e，f(g))，d)，当用左子女一右兄弟链表表示时，右指针 域非空的结点个数为 [ ] A．1 B．2 C．3 D．4 56.向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为 [ ] A．O(1) B．O(log2n) C．O(n) D．O(nlog2n) 57.具有n个顶点的有向无环图最多可包含[ ]条有向边。 A．n—1 B．n C．n(n—1)／2 D．n(n–1) 58.图的广度优先搜索类似于树的[ ]次序遍历。 A.先根 B.中根 C.后根 D.层次 59.如果将所有中国人按照生日(不考虑年份，只考虑月、日)来排序，那么使用下列排序算法中[ ] 算法最快。 A.归并排序 B.希尔排序 C.快速排序 D.基数排序 60.下面算法的时间复杂度为[ ] int f(unsigned int n) { if(n==0||n==1)return 1; else return n * f(n-1); } A.0(1) B.O(n) C.O(n2) D.O(n!) 61.队列的删除操作是在( )进行。 [ ] A.队首 B.队尾 C.队前 D.对后 62.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1／8， 搜索后面5个元素的概率相同，均为3／40，则搜索任一元素的平均搜索长度为 [ ] A．5.5 B．5 C. 39／8 D.19／4 63.每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种 排序方法叫做( )排序。 [ ] A.插入 B.堆 C.快速 D.归并 64.在一个长度为n的顺序表中顺序查找一个值为x的元素时。在等概率的情况 下，搜索成功时间元素的平均比较次数为 [ ] A.n B.n/2 C.(n+l)/2 D.(n-1)/2 65.在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是 [ ] A.-1~1 B.-2~2 C.1~2 D.0~1 66.在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号 为( )假定树根结点的编号为0。 [ ] A.2i B.2i-1 C.2i+1 D.2i+2 67.在散列查找中，平均查找长度主要与( )有关。 [ ] A.散列表长度 B.散列元素的个数 C.装填因子 D.处理冲突方法 68.带头结点的单链表first为空的判定条件是 [ ] A.first==NULL; B.first->link==NULL C.first->link==first D.first!=NULL 69.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为( )个。 [ ] A.n+2 B.n2 C.n D.2n 70.设有一个广义表A((x，(n，b))，(x，(9，b)，y)),运算Head(Head(Tail(A))) 的执行结果为 [ ] A．x B (a，b) C.(x，(a ，b)) D. y 71.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要( ）条边。 [ ] A.n+2 B.n-1 C.n D.2n 72.已知L是一个不带表头的单链表的头指针，在表首插入结点*p的操作是 [ ] A.p=L; p->link=L; B.p->link=L; p=L; C.p->link=L; L=P; D.L=p; p->link=L; 73.在平均情况下速度最快的排序方法为 [ ] A.直接选择排序 B.归并排序 C.堆排序 D.快速排序 74.设循环队列的结构是： struct Queue { DataType data[MaxSize]; int front, rear; }; 若有一个Queue类型的队列Q．试问判断队列满的条件应为 [ ] A.Q. from==Q, rear; B.Q. front==Q. rear==MaxSize; C.Q. front+Q, rear= =MaxSize; D.Q. front==(Q, rear+l) % MaxSize; 三、填空题： 1.若频繁地对线性表进行插入与删除操作，该线性表应采用______________存储结构。 2.在双链表中，每个结点有两个指针域，一个指向____ __，另一个指向___ __。 3.空格串是__ __，其长度等于_ ___。 4.一个图的表示法是唯一的，而表示法是不唯一的。 5.对于长度为n的关键字有序的线性表，若进行顺序查找，则时间复杂度为__ __；若采用二分法查找， 则时间复杂度为_ ___； 6.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。 7.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢,在进 行运算时，可能发生栈的下溢。 8.在双向链表中，每个结点有两个指针域，一个指向____ __，另一个指向___ __。 9.由一棵二叉树的前序序列和可唯一确定这棵二叉树。 10.折半查找的存储结构仅限于___ _，且是_ ___。 11.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为和。 12.分析下面算法（程序段），给出最大语句频度___ _，该算法的时间复杂度是___ _。 { for (i=1; i<=n; i++) for (j=1; j<=i ; j++) cout< } 13.稀疏矩阵的压缩存储结构，一种是________表示法，而另一种是________表示法。 14.数据结构包括____________和____________。前者可以用一个二元组B=(K,R)，来表示，K是 ____________，R是____________。 15.线形表有两种存储结构:顺序存储结构和链式存储结构，请就这两种存储结构完成下列填充： ____________可以随机存取；____________不可以随机存取; ____________插入和删除比较方便。 16.在单链表中，删除指针P所指向结点的后续结点的语句____________。 17.删除带头结点的单循环链表Head的第一个结点的操作是____________；删除不带头结点的单循环链 表的第一个结点的操作是____________。 18.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维数组b[m][n] 中所有元素值的时间复杂度为________。 19.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和三 项。 20.对于二分查找所对应的判定树，它既是一棵________，又是一棵________。 21.在一个图中，所有顶点的度数之和等于所有边数的________倍。 22.当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层调整，直到被调整到 位置为止。 23.递归算法包括____________和 ____________两部分。 24.在树中存在唯一的一个结点，我们把这个结点称为________。 25.线性表的两种存储结构一种为顺序存储，另一种为________。 26.队列允许在________进行删除，在________进行插入。 27.叶子结点的度为________，满2 叉树的第k 层具有________个结点。 28.图的遍历可分为遍历，遍历。 29.在线性结构中，第一个结点________前驱结点，其余每个结点有且只有________个前驱结点；最后一 个结点________后续结点，其余每个结点有且只有________个后续结点。 30.在树形结构中，树根结点没有________结点，其余每个结点有且只有________个直接前驱结点，叶子 结点没有________结点，其余每个结点的直接后续结点可以________。 31.在图形结构中，每个结点的前驱结点数和后续结点数可以________。 32.线性结构中元素之间存在________关系，树形结构中元素之间存在________关系，图形结构中元素之 间存在________关系。 33.算法的五个重要特性是________,________,________,________,________。 34.在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作： q=head; while (q->next!=p) q=q->next; s= new Node; s->data=e; q->next= ; //填空 s->next= ; //填空 35.在一个单链表中删除p所指结点的后继结点时，应执行以下操作： q= p->next; p->next= _ ___; //填空 delete ; //填空 36.两个串相等的充分必要条件是____。 37.二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200， 则A[6][12]的地址是____。 38.二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存 储地址是1000，则A[18][9]的地址是____。 39.求下列广义表操作的结果： (1) GetTail[GetHead[((a,b),(c,d))]]; ________ (2) GetTail[GetHead[GetTail[((a,b),(c,d))]]] ________ 40.n个顶点的连通图至少____条边。 41.在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____， 否则等于____。 42.已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 43.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。 44.如果含n个顶点的图形成一个环，则它有________棵生成树。 45.一个非连通无向图，共有28条边，则该图至少有________个顶点。 46.遍历图的过程实质上是________。采用邻接矩阵时，BFS遍历图的时间复杂度为________，DFS遍历 图的时间复杂度为________，两者不同之处在于________，反映在数据结构上的差别是________。47.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处 理冲突时的平均查找长度为____。 48.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。 49.折半查找的存储结构仅限于____，且是____。 50.假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找 成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。 51.对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度 为____； 52.已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行________ 次查找可确定成功；查找47时，需进行________次查找成功；查找100时，需进行________次查找才能确定不成功。 53.二叉排序树的查找长度不仅与________有关，也与二叉排序树的________有关。 54.一个无序序列可以通过构造一棵________树而变成一个有序树，构造树的过程即为对无序序列进行排 序的过程。 55.在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调 用而使用的栈所能达到的最大深度为____，共需递归调用的次数为____，其中第二次递归调用是对____一组记录进行快速排序。 56.在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取____方法，其次选取____方 法，最后选取____方法；若只从排序结果的稳定性考虑，则应选取____方法；若只从平均情况下排序最快考虑，则应选取____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取____方法。 57.属性与服务相同的对象构成类，类中的每个对象称为该类的________· 58.在类的继承结构中，位于上层的类叫做________，其下层的类则叫做________类． 59.若设串S＝“documentHash．doc＼O”，则诙字符串S的长度为________· 60.线性表的链接存储只能通过________顺序访问。 61.设链栈中结点的结构为(data，link)，栈顶指针为top，则向该链栈插入、—个新结点*p时，应依 次执行________和________操作。 62.广义表的深度定义为广义表中括号被嵌套的________· 63.在一棵高度为h的完全二叉树中，最少含有________个结点．假定树根结点的高度为O． 64.从有序集合(12，10，30，43，56，78，02，95)中折半搜索56和98元素时，其搜索长度分别为________ 和。 65.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。 66.在一棵高度为h的3叉树中，最多含有_______结点。 67.假定一棵二叉树的结点数为18，则它的最小深度为________，最大深度为_______。 68.在一棵二叉搜索树中，每个分支结点的左子树上所有的结点的值一定___________该结点的值，右子 树上所有结点的值一定__________该结点的值。 69.当向一个小根堆插入一个具有最一小值的元素时，该元素需要逐层_______调整，直到被调整到 _______位置为止。 70.表示图的三种存储结构为_________________、________________和________________。 71.对用邻接距阵表示的具有n个顶点和e条边的图形进行任一种遍历时，其时间复杂度为__________， 对用邻接表表示的图进行任一种遍历时，其时间复杂度为______________。 72.从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分别为 ___________和__________。 73.假定对长度n=144的线性表进行索引查找，并假定每个子表的长度均为n,则进行索引查找的平均查 找长度为__________，时间复杂度为___________。 74.一棵B-树中的所有叶子结点均处在_____________上。 75.n个(n>o)顶点的连通无向图中各顶点的度之和最少为。 76.设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为。 77.给定一组数据对象的关键码为{46，79，56，38，40，84}，则利用堆排序方法建立的初始最大堆的堆 首和堆尾的关键码分别为和。 78.在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引；若对应数据对象 表中的若干表项，则称此索引为索引。 四、计算与算法应用题： 1.给定表（119，14，22，1，66，21，83，27，56，13，10）,请按表中元素的顺序构造一棵平衡二 叉树，并求其在等概率情况下查找成功的平均长度。 2.对下面的有向图从顶点V1开始进行遍历，试画出遍历得到的DFS生成森林和BFS生成森林。 V1 V3V4V2 V5 V6V7V8 3.已知一个有向图的顶点集V和边集G分别为： V={a,b,c,d,e,f,g,h} E={ 假定该图采用邻接矩阵表示，则分别写出从顶点a出发进行深度优先搜索遍历和广度优先搜索遍历得到的顶点序列。 4.已知一棵二叉树的中序和后序序列如下，求该二叉树的高度(假定空树的高度为-1)和度为2、度为 l 及度为0的结点个数。 中序序列：c，b，d，e，a，g，i，h，j，f 后序序列：c，e，d，b，i，j，h，g,f，a 高度： 度为2的结点数： 度为1的结点数： 度为0的结点数： 5.设散列表的长度为13，散列函数为H（h）= k%13，给定的关键码序列为19，14，23，01，68，20， 84，27。试画出用线性探查法解决冲突时所构成的散列表。 0 1 2 3 4 5 6 7 8 9 10 11 12 6.对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。 (1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。 7.已知一个带权图的顶点集V和边集G分别为： V={0，l，2，3，4，5，6}； E={(0，1)19，(0，2)10，(0，3)14，(1，2)6，(1，5)5，(2，3)26，(2，4)15，(3，4)18，(4，5)6，(4，6)6，(5，6)12)；其中顶点对后的值表示对应边的权。 试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各项点的最短路径。 8.如图所示二叉树，回答下列问题。 9.对于下图，若按照克鲁斯卡尔算法产生最小生成树，写出得到的各条边的次序。 10.画出在一个初始为空的AVL树中依次插入3,1,4,6,9,8,5,7时每一插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。 11.已知一组记录的排序码为（ 46 ， 79 ， 56 ， 38 ， 40 ， 80, 95 ， 24 ），写出对其进行快速排序的每一次划分结果。 12.一个线性表为 B= （ 12 ， 23 ， 45 ， 57 ， 20 ， 03 ， 78 ， 31 ， 15 ， 36 ），设散列表为 HT[0..12] ，散列函数为 H （ key ） = key % 13 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 13.已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJ ，中序遍历的结果是 EBCDAFHIGJ ，试写出这棵二叉树的后序遍历结果。 14.假定对线性表(38，25，74，52，48，65，36)进行散列存储，采用H(K)=K％9作为散列函数，若分别采用线性探查法和链接法处理冲突，则对应的平均查找长度分别为和。 15.假定一组记录的排序码为(46，79，56，38，40，80，25，34，57，21)，则对其进行快速排序的第一次划分后又对左、右两个子区间分别进行一次划分，得到的结果为：。 16.下图是带权的有向图G的邻接表表示法。从结点V1出发，深度遍历图G所得结点序列为（ A ），广度遍历图G所得结点序列为（ B ）；G的一个拓扑序列是（ C ）；从结点V1到结点V8的最短路径为（ D ）；从结点V1到结点V8的关键路径为（ E ）。 其中A、B、C的选择有： (1)V1,V2,V3,V4,V5,V6,V7,V8 (2)V1,V2,V4,V6,V5,V3,V7,V8 (3)V1,V2,V4,V6,V3,V5,V7,V8 (4)V1,V2,V4,V6,V7,V3,V5,V8 (5)V1,V2,V3,V8,V4,V5,V6,V7 (6)V1,V2,V3,V8,V4,V5,V7,V6 (7)V1,V2,V3,V8,V5,V7,V4,V6 D、E的选择有： ①V1,V2,V4,V5,V3,V8 ②V1,V6,V5,V3,V8 ③V1,V6,V7,V8 ④V1,V2,V5,V7,V8 17.画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 18.已知如图所示的有向网，试利用Dijkstra算法求顶点1到其余顶点的最短路径，并给出算法执行过程中各步的状态。 19.假定一棵普通树的广义表表示为a(b(e),c(f(h,i),g),d),分别写出先根，后根，按层遍历的结果。 先根： 后根： 按层： 20.已知一个带权图的顶点集V和边集G分别为： V={0，1，2，3，4，5，6，7}； E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9}； 则求出该图的最小生成树的权。 最小生成树的权： 21.对于线性表（18，25，63，50，41，32，90，66）进行散列存储时，若选用H（K）=K%11作为散列 函数，则散列地址为0的元素有______个，散列地址为3的元素有______个，散列地址为8的元素有______ 个。 22.假定一组记录的排序码为（46，79，56，38，40，80，25，34），在对其进行快速排序的过程中， 进行第一次划分后得到的排序码序列为 ________________________________。 23.将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出 每插入一个关键码后的二叉搜索树。 24.设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的平均比较次 数不超过2次。试问散列表需要设计多大？（设α是散列表的装载因子，则有ASLsucc=（1+1/（1-α））/ 2）。 25.设待排序文件的关键码为（86，75，50，40，90，33，15，42）进行希尔排序（按关键码值递增顺 序），请给出一趟排序后的结果。 26.以数据集{7，19，2，6，32，3，21，10}为叶子结点的权值， （1）构造一棵哈夫曼树（要求写出构造树时的各具体步骤）； （2）编写各叶子结点的哈夫曼编码； 27.已知如图所示的有向图，请给出该图的: (1)每个顶点的入/出度； (2)邻接矩阵； (3)邻接表。 另外，还要求大家熟练掌握Huffman树的构建方法，树与二叉树之间的转换，以及各种排序方法的排 序过程。 五、算法设计题： 1.已知深度为h的二叉树以一维数组BT(1:2h-1)作为其存储结构。请写一算法，求该二叉树中叶结点 的个数。 2.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找item带回 整个结点的值并返回true，否则返回false。 bool Find（BtreeNode*BST，ElemType&item） 3.根据下面函数原型，编写一个递归算法，统计并返回以BT为树根指针的二叉树中所有 叶子结点的个数。 int Count(BTreeNode * BT)； 4.设A=(a1,...,am)和B=(b1,...,bn)均为顺序表，A'和B'分别为A和B中除去最大共同前缀后的子表。若 A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A 5.已知单链表a和b的元素按值递增有序排列, 编写算法归并a和b得到新的单链表c，c的元素按值 递减有序。 6.编写递归算法，对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 7.编写算法判别T是否为二叉排序树. 8.已知带头结点的单链表是一个递增有序表，试写一算法，删除表中值大于min且小于max的结点（若 表中有这样的结点），同时释放被删除结点的空间，这里min和max是两个给定的参数。 9.编写一个算法，返回二叉查找树中的关键字最小的元素值。 10.写出向以BST 为树根指针的二叉搜索树上插入值为item 的结点的递归算法。 void Insert(ABTList BST, const ElemType & item) { 11.已知二叉树中的结点类型BinTreeNode 定义为： struct BinTreeNode{chardata;BinTreeNode*left ， *right ；)； 其中data 为结点值域，left 和right 分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值也相同时才被认为相等。 int BTreeEqual(BinTreeNOde*T1，BinTreeNode*T2)； 12.对于结点类型为LNode 的单链表，编写出下列每个算法。 (1) 删除单链表中的第i 个结点。 (2) 在有序单链表中插入一个元素x 的结点。 (3) 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止 运行。 (4) 统计出单链表中结点的值等于给定值x 的结点数。 13.已知一棵具有n 个结点的完全二叉树被顺序存储于一维数组的A[1] A[n]元素中，试编写一个算法打印出编号为i 的结点的双亲和所有孩子。 六、阅读下列算法，分析它的作用 1.阅读下列算法，说明该算法的作用。 int LinkList::sum( ) { int x;NodeType *p;p=Head->next; while(p!=NULL) { x++; p=p->next; } return x; } // pop 2.读下述算法，说明本算法完成什么功能。 void Btree ::inordern( bnode *p, int &n ) { if ( p!=NULL) { inordern( p->lch, n); if ( p->lch==NULL && p->rch==NULL) n++; inordern( p->rch, n); } } // inordern 3.下列函数是二叉排序树的什么算法？如果K 值为5，针对下图所示二叉树，运行下列算法，输出是什么？比较几次得到结果？ Void Bstree::Search( KeyType K) { int flag = 0; BstNode *q=root, *p = NULL; while((q!=NULL)&&(flag==0)) { if(q->key==K) flag = 1; else if ( K else { p = q; q = q->rch; } } if(flag == 0) cout<<"\n 查找失败，无此结点！\n"; else cout<<"\n 查找成功，找到："< } 4.假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。 # include < iostream.h> # include < stdlib.h > consst int stackmaxsize = 30; typedef int elemtype; struct stack { elemtype stack [stackmaxsize]; int top; }; # include “stack.h” Void main ( ) { stack a; initstack(a); int x; cin >>x; 2 while (x! = -1) { push (a, x ); cin >>x; } while (!stackempty (a)) cout < cout < } 该算法的输出结果为： __________________________________________________________. 参考答案 一、判断题： 1.√ 2.× 3.√ 4.× 5.√ 6.√ 7.× 8.× 9.× 10.× 11.× 12.√ 13.×14.√ 15.× 16.√ 17.× 18.× 19.× 20.× 21.√ 22.× 23.√ 24.√ 25.× 26.× 27.× 28.√ 29.× 30.× 31.√ 32.√ 33.× 34.× 35.√ 36.√ 37.√ 38.× 39.√ 二、单项选择题： 1.A 2.B 3.B 4.D 5.C 6.A 7.C 8.C 9.C 10.B 11.A 12.C 13.B 14.D 15.A 16.A 17.D 18.C 19.C 20.A 21.B 22.A 23.B 24.D 25.C 26.B 27.C 28.D 29.B 30.A 31.A 32.B 33.D 34.A 35.C 36.C 37.D 38.C 39.D 40.A 41.B 42.C 43.D 44.C 45.A 46.A 47.B 48.B 49.C 50.C 51.B 52.D 53.B 54.D 55.C 56.B 57.C 58.D 59.D 60.B 61.A 62.C 63.B 64.C 65.A 66.C 67.C 68.B 69.D 70.A 71.B 72.C 73.D 74.D 三、填空题： 1.链式存储结构 2.前驱结点，后继结点 3.由一个或多个空格字符组成的串，其包含的空格个数 4.邻接矩阵，邻接表 5.O（n）， O(log2n) 6.1044 7.入栈（插入），出栈（删除） 8.前驱结点，后继结点 9.中序序列 10.顺序存储结构，有序的 11.n ， n-1 12.最大语句频度: n(n+1)/2 ，时间复杂度： O (n2) 13.三元组表，十字链表 14.逻辑结构和物理结构数据元素的集合数据元素之间关系的集合 15.顺序存储结构链式存储结构顺序存储结构链式存储结构链式存储结构 16.p->next=p->next->next 17.Head->next=Head->next->next Head=Head->next 18.O(n)、O(m*n) 19.行号、列号、元素值 20.二叉搜索树、理想平衡树 21. 2 22.向上、堆顶 23.递推，回归 24.根结点 25.链式存储 26.队首，队尾 27.0 ，2k-1 28.深度，广度 29.没有、1、没有、1 30.前驱、1、后续、任意多个 31.任意多个 32.一对一、一对多、多对多 33.有穷性、确定性、可行性、输入、输出 34.s, p 35.q->next, q 第九章习题 一、选择题（1-10小题为多选题，11-13小题为单选题） 1. 在SQL Server2000中属于表级完整性约束的是（AC ）。 A）实体完整性约束B）域完整性约束C）参照完整性约束D）以上三者均是 2. 在SQL Server2000中实现数据完整性的主要方法有（ABCD ）。 A）约束B）默认C）规则D）触发器 3. 在SQL Server2000的数据完整性控制中属于声明数据完整性的是（ABC ）。 A）约束B）默认C）规则D）触发器 4. 在SQL Server2000的数据完整性控制中属于过程数据完整性的是（AD）。 A）存储过程B）默认C）规则D）触发器 5. 在SQL Server中，以下（AB）约束属于域完整性约束。 A）DEFAULT B）CHECK C）NULL D）FOREIGN KEY 6. SQL Server2000数据库系统中一般采用（ABCD ）以及密码存储等技术进行安全控制。 A）用户标识和鉴别B）存取控制C）视图D）触发器 7. SQL Server2000使用权限来加强系统的安全性，语句权限适用的语句有（B ）。 A）EXECUTE B）CREATE TABLE C）UPDATE D）SELECT 8. 有关登录帐户、用户、角色三者的叙述中正确的是（）。 A）登录帐户是服务器级的，用户是数据库级的 B）用户一定是登录帐户，登录帐户不一定是数据库用户 C）角色是具有一定权限的用户组 D）角色成员继承角色所拥有访问权限 9. SQL Server2000的安全性管理包括（）。 A）数据库系统登录管理B）数据库用户管理 C）数据库系统角色管理D）数据库访问权限的管理。 10. SQL Server2000使用权限来加强系统的安全性，通常将权限分为（AC）。 A）对象权限B）用户权限C）语句权限D）隐含权限 11. SQL Server 2000提供了4层安全防线，其中SQL Server2000通过登录账号设置来创建附加安全层，用户只有登录成功，才能与SQL Server2000建立一次连接，属于（B ）。 A）操作系统的安全防线B）SQL Server2000的运行安全防线 C）SQL Server2000数据库的安全防线D）SQL Server2000数据库对象的安全防线 12. SQL Server2000中，为便于管理用户及权限，可以将一组具有相同权限的用户组织在一起，这一组具有相同权限的用户就称为（B ）。 A）帐户B）角色C）登录D）SQL Server用户 13. 在SQL Server中，有关页的叙述中正确的是（）。 A）页是除行外的最小数据单位 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 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 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n） 1?在数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的（）阶段。 A需求分析 B概念设计 C逻辑设计 D物理设计 参考答案 B 数据库设计步骤： （1）规划（必要性、可行性，总目标） （2）需求分析（分析用户活动，产生业务流程图；确定系统范围，产生系统范围图；分析用户活动涉及的数据，产生数据流程图；分析系统数据，产生数据字典。）（3）概念设计（设计出独立于计算机硬件和DBMS的概念模式。E-R模型是主要设计工具） （4）逻辑结构设计（把概念设计阶段设计好的全局E-R模式转换成与选用的具体机器上的DBMS所支持的数据模型相符合的逻辑结构，包括数据库模式和外模式）（5）数据库的物理设计（对于给定的数据模型选取一个垠适合应用环境的物理结构的过程。数据库的物理结构主要指数据库的存储记录格式、存储记录安排和存取方法）（6）数据库的实现（建立实际数据库结构；装入试验数据对应用程序进行调试；装入实际数据，进入试运行状态） （7）数据库的运行与维护（维护数据库的安全性与完整性；监测并改善数据库运行性能; 根据用户要求对数据库现有功能进行扩充；及时改正运行中发现的系统错误） 2.关于数据库概念设计阶段的工作目标，下列说法错谋的是 A定义和描述应用系统涉及的信息结构和范围 B定义和描述应用系统中数据的属性特征和数据之间的联系 C描述应用系统的数据需求 D描述需要存储的记录及其数量 参考答案 3. SQL Server 2000的字符型系统数据类型主要包括（）。 A int、money、char B char> varchar、text C datetime、binary> int D char、varchar> int 参考答案 B 4. 具有联系的相关数据按一定的方式组织排列，并构成一定的结构，这种结构即（）。 A数据模型 B数据库 C关系模型 D数据库管理系统 参考答案 A 5. 在数据库系统中，下列哪个映像关系用于提供数据与应用程序间的逻辑独立性？ A外模式/模式 B模式/内模式 C外模式/内模式 D逻辑模式/内模式 参考答案 B 6. 关系模型的数据结构是 A树 B图 C表 D二维表 参考答案 D 7. 数据字典是数据库管理系统的重要组成部分，其中存储的各类信息通常由 A数据库管理员维护 B程序员维护 C数据库管理系统维护 D—般用户维护 参考答案 A 8. E-R图用于描述数据库的 1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。 3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？ 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 数据结构》期末考试试题及答案 ( 2003-2004 学年第 2 学期 ) 单项选择题 1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 7．图的 Depth-First Search （DFS ） 遍历思想实际上是二叉树（ 法的推广。 （A ）、先序 （ B ）、中序 （C ）、后序 （D ）、层序 8．在下列链队列 Q 中，元素 a 出队的操作序列为（ p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9． Huffman 树的带权路径长度 WPL 等于（ c （ A ）、除根结点之外的所有结点权值之和1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 （ c ）。 （A ） 、正确性 （B ）. 可行性 （C ）. 健壮性 2．设 S 为 C 语言的语句 ,计算机执行下面算法时， for （i=n-1 ； i>=0 ； i--） for （j=0 ；j 有职工工资表(职工号、姓名、日期、基本工资、奖金、工资合计)，其中“工资合计”等于同一行数据的“基本工资”与“奖金”之和，在职工工资表中插入一行数据时(设一次只插入一行数据)能实现自动计算“工资合计”列的值的代码是( )。 A ALTER TABLE 职工工资表 ADD CHECK(工资合计=基本工资+奖金) B UPDATE 职工工资表SET 工资合计=基本工资+奖金 C INSERT INTO 职工工资表(工资合计) VALUES (基本工资+奖金) D CREATE TRIGGER tgz ON 职工工资表 FOR INSERT AS UPDATE 职工工资表SET 工资合计=a.基本工资+a.奖金 FROM 职工工资表 a JOIN INSERTED b ON a.职工号=b.职工号 AND a.日期=b.日期 参考答案 D 在SQL Server中，有教师表（教师号，姓名，职称，工资）。现要为“教授”的工资增加400。下列语句中正确的是( )。 A UPDATE 教师表SET 工资=工资+400 WHERE 职称= ′教授′ B UPDATE 教师表WITH 工资=工资+400 WHERE 职称= ′教授′ C UPDATE FROM 教师表SET 工资=工资+400 WHERE 职称= ′教授′ D UPDATE 教师表SET 工资+400 WHERE 职称= ′教授′ 参考答案 A 在为student_db数据库的St_Info表录入数据时，常常需要一遍又一遍地输入“男”到学生“性别”列，以下（）方法可以解决这个问题。 A 创建一个DEFAULT约束（或默认值） B 创建一个CHECK约束 C 创建一个UNIQUE约束（或唯一值） D 创建一个PRIMARY KEY约束（或主键） 数据结构考试复习题集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08] 复习题集 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 “数据结构”期末考试试题 一、单选题(每小题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条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) 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的线性表进行索引顺序查找，并假定每个子表的长度均 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 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. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 成绩表grade中字段st_id代表学号，score代表分数，以下（）语句返回成绩表中的最低分。 A SELECT max(score) FROM grade B SELECT TOP 1 score FROM grade ORDER BY score ASC C SELECT st_id, MIN(score) FROM grade D SELECT TOP 1 score FROM grade ORDER BY score DESC 参考答案 B 有教师表(教师号，姓名，所在系，工资)，找出系内教师平均工资高于全体教师平均工资的系信息，正确语句是 A SELECT 所在系, AVG(工资) FROM 教师表 WHERE AVG(工资)>(SELECT AVG(工资) FROM 教师表) B SELECT 所在系,AVG(工资) FROM 教师表 WHERE AVG(工资)>(SELECT AVG(工资) FROM 教师表) GROUP BY 工资 C SELECT 所在系, AVG(工资) FROM 教师表 GROUP BY 所在系 HAVING AVG(工资)>(SELECT AVG(工资) FROM 教师表) D SELECT 所在系,AVG(工资) FROM 教师表 GROUP BY 所在系 WHERE AVG(工资)>(SELECT AVG(工资) FROM 教师表) 参考答案 C 有教师表(教师号，姓名，职称，所在系)和授课表(教师号，课程号，授课学年，授课时数)，同一门课程可由多个教师讲授，同一个教师也可讲授多门课程，查询从未被“教授”讲授过的课程的课程号，正确的语句是 A SELECT 课程号FROM 授课表 a JOIN 教师表 b ON a.教师号=b.教师号WHERE 职称!=′教授′ B SELECT 课程号FROM 授课表 a RIGHT OUTTER JOIN 教师表 b ON a.教师号=b.教师号 2005年－2006学年第二学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清晰姓名、班号和学号），需写清晰题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2.链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3.在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是d 。 A.不带头结点的单链表 B.带头结点的单链表 C.循环双链表 D.顺序表 解D。 5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。A.edcba B.decba C.dceab D.abcde 答：C。 6.循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7.两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是 c 。 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 答：C。 9.以下序列不是堆（大根或小根）的是 d 。 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} 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆中南大学数据库习题 复习题目【爆款】.doc
数据结构复习题(附答案)
数据结构模拟题(开卷)
数据结构考试试题及答案
中南大学数据库考试题库
数据结构 期末考试复习题及答案
数据结构模拟试题及答案
《数据结构》期末考试试题及答案
中南大学数据库题库03数据表
数据结构考试复习题
《数据结构C》模拟试题
数据结构C语言版期末考试试题(有答案)
数据结构复习题附答案
《数据结构》模拟试卷一及答案
数据结构期末考试试题及答案
中南大学数据库题库04数据查询
数据结构期末考试试题含复习资料
数据结构模拟试卷(含答案)
相关主题
文本预览