复习题集
一判断题
（）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.栈和队列具有相同的逻辑特性。
（）28.树形结构中每个结点至多有一个前驱。
（）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。
（）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。
（）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。
（）32.顺序查找方法只能在顺序存储结构上进行。
（）33.折半查找可以在有序的双向链表上进行。
（）34.满二叉树中不存在度为1的结点。
（）35.完全二叉树中的每个结点或者没有孩子或者有两个孩子。
（）36.对n个元素执行快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。
（）37.在有向图中，各顶点的入度之和等于各顶点的出度之和。
一、选择题
（）1. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：
A) 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C) 删除第i个结点（1≤i≤n）
B) 在第i个结点后插入一个新结点（1≤i≤n）D) 将n个结点从小到大排序（）2. 算法分析的目的是：
A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性
（）3. 算法分析的两个主要方面是：
A) 空间复杂性和时间复杂性B) 正确性和简明性
C) 可读性和文档性D) 数据复杂性和程序复杂性
（）4. 计算机算法指的是：
A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法
（）5. 计算机算法必须具备输入、输出和等5个特性。
A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性
（）6. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是: （A）110 （B）108 （C）100 （D）120
（）下列选项中与数据存储结构无关的术语是：
A.顺序表
B.链表
C.链队列
D.栈
（）7. 链接存储的存储结构所占存储空间：
（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
（B）只有一部分，存放结点值
（C）只有一部分，存储表示结点间关系的指针
（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数
（）8. 带头结点的单链表head，链表为空的判定条件是
(A)head == NULL (B) head->next ==NULL ( C) head->next ==head (D) head!=NULL
（）9. 一个栈的输入序列为1，2，3，…，n，若输出序列的第一个元素是n，输出第i（1≤i≤n）个元素是。
A) 不确定B) n－i＋1 C) i D) n－i
（）10. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。
A) (rear＋1)% n==front B) rear===front C) rear＋1==front D) (rear－l) % n==front （）11. 循环队列A[0..m－1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是:
(A) (rear－front＋m)%m (B) rear－front＋1 (C) rear－front－1 (D) rear－front
除一个元素，再加入两个元素后，rear 和front 的值分别为: (A) 1和5 (B) 2和4 (C) 4和2 ( D) 5和1 （ ）13. 按照二叉树的定义，具有3个结点的二叉树有（ ）种。
A) 3 B) 4 C) 5 D) 6 [利用排列组合知识来做]
（ ）14. 若一棵二叉树中度为l 的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是: (A) 4 (B) 5 (C) 7 (D) 8
（ ）15. 具有n(n>0)个结点的完全二叉树的深度为:
(Ａ) ?log 2(n)? (Ｂ) ? log 2(n)? (Ｃ) ? log 2(n) ?+1 (Ｄ) ?log 2(n)+1?
（ ）16. 对一个满二叉树，m 个叶子，n 个结点，深度为h ，则:
(A) n = h+m (B) h+m = 2n (C) m = h-1 (D) n = 2h-1
（ ）17．在高度为h 的完全二叉树中，表述正确的是（ ）
A.度为0的结点都在第h 层上
B.第i(1≤i C.第i(1≤i D.不存在度为1的结点 （ ）18. 深度为5的二叉树至多有（ ）个结点。 A) 32 B) 31 C) 16 D) 10 （ ）19. 用邻接表表示图进行深度优先遍历时，通常采用( )结构来时实现算法。 A) 栈 B) 队列 C) 树 D) 图 （ ）20. 对N 个记录作顺序查找时，当查找成功时，平均查找长度是（ ）。 A) N 2 B) N 2/2 C) N D)（N ﹢1)/2 （ ）21. 当一个有n 个顶点的图用邻接矩阵A 表示时，顶点V i 的度是（ ）。 (A) ∑=n i j i A 1 ],[ B) ∑=n j j i A 1],[ C)∑=n i i j A 1],[ D)∑=n i j i A 1],[+∑=n j i j A 1 ],[ （ ）22．某算法的时间复杂度为O(2n )，表明该算法的（ ） A.问题规模是2n B.执行时间等于2n C.执行时间近似与2n 成正比 D.问题的规模近似与2n 成正比 （ ）23．“二叉树为空”意味着二叉树（ ） A.由一些没有赋值的空结点构成 B.根结点没有子树 C.不存在 D.没有结点 （ ）24．数据结构的研究内容不涉及（ ） A.数据如何组织 B.数据如何存储 C.数据的运算如何实现 D.算法用什么语言描述 （ ）25．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 （ ）26．数据采用顺序存储，要求（ ） A.存储的是属于线性结构的数据 B.根据结点值的大小，有序存放各结点 C.按存储单元地址由低到高的顺序存放各结点 D.各结点存放方法有规律，能隐含表示结点间的逻辑关系 （ ）27．一个顺序表所占存储空间大的大小与（ ）无关 A.顺序表长度 B.结点类型 C.结点中各字段的类型 D.结点存放顺序 （ ）28．数据采用链接存储，要求（ ） C.结点的最后一个字段是指针型的字段 C.每个结点有多少个后继，就设多少个指针字段 （）29．算法的时间复杂度与（）有关 A.问题规模 B.计算机硬件性能 C.编译程序质量 D.程序设计语言 （）30．在程序中，为了设置一个空的顺序表，必须（） A.给各数组元素赋空值 B.给各顺序表元素赋空值 C.给表示顺序表长度的变量赋初始值 D.给数组变量名赋初始值 （）31．若变量H是某个带表头结点循环单向链表的表头指针，则在该链表最后的一个结点的后继指针域中存放的是（） A.H的地址 B.H的值 C.表头结点的值 D.首元结点的地址 （）32．栈和队列的共同点在于（） A.逻辑特性 B.存储结构 C.运算方法 D.元素类型 （）33．栈和队列的共同点在于（） A.都对存储方法作了限制 B.都是只能进行插入、删除运算 C.都对插入、删除的位置作了限制 D.都对插入、删除两中操作的先后顺序作了限制 （）34．若5个元素的进栈序列是1,2,3,4,5，则不可能得到出栈序列（） A.1，2，3，4，5 B.3，4，2，5，1 C.4，2，1，3，5 D.5，4，3，2，1 （）35．顺序循环队列中是否可以插入下一个元素，（） A.与队首指针和队尾指针的值有关 B.只与队尾指针的值有关，与队首指针的值无关 C.只与数组大小有关，与队首指针和队尾指针的值无关 D.与曾经进行过多少次插入操作有关 （）36．在顺序队列中，元素的排列顺序（） A.由元素插入队列的先后顺序决定 B.与元素值的大小有关 C.与队首指针和队尾指针的取值有关 D.与数组大小有关 （）37．在高度为h的完全二叉树中，（） A.度为0的结点都在第h层上 B.第i(1≤i C.第i(1≤i D.不存在度为1的结点 （）38．一颗二叉树如图所示，其中序遍历的序列为： B. DGBAECHF C. GDBEHFCA D. ABCDEFGH （）39．采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A．先序遍历B．中序遍历C．后序遍历D．按层遍历 （）40．采用邻接表存储的图的广度优先遍历算法类似于二叉树的 （）41.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的 关键字序列是 A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68) C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83) 二、填空题 1．数据结构包括数据的、数据的和数据的这三个方面的内容。 2．下面程序段的时间复杂度是。 i ＝0； while（i<=n）i = i * 3； 3．在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 4．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是，应采用存储结构。 5．在n个结点的单链表中要删除已知结点*p，需找到它的的地址，其时间复杂度为。6．已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾结点，试从下列提供的答案中选择合适的语句序列。 删除P结点的直接后继结点的语句序列是。 删除P结点的语句序列是。 (1) P = P->next ; (2) P->next = P; (3) P->next = P->next->next (4) P->next = P->next->next; (5) while(P!=NULL) P = P->next ; (6) while(Q->next != NULL) {P = Q; Q=Q->next;} (7) while(P->next != Q) P = P->next; (8) while(P->next->next != Q) P = P->next; (9) while(P->next->next != NULL) P = P->next; (10) Q = P; (11) Q = P->next; (12) P = L ; (13) L = L->next; (14) free(Q); 7．栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 8．设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则 栈S的容量至少是。 9．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为。 10．数据的逻辑结构可以分为和两大类。 11．数据的运算用表示。 12．逻辑上相邻的结点在存储器中也相邻，这是存储结构的特点。 13．在长度为n的顺序表上实现定位操作，其算法的时间复杂度为。 14．为了实现随机访问，线性结构应该采用存储。 15．在长度为n的顺序表中插入一个元素，最多要移动个元素。 17．在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用栈。 18．在树形结构中，如果某结点，则称该结点为根结点；如果某结点，则称该结点为叶子。 19．在树形结构中，每个结点最多只有一个。 20．由3个结点所构成的二叉树有种形态。 21．二叉树的前序遍历按如下三个步骤进行：；；。 22．二叉树的中序遍历按如下三个步骤进行：；；。23．在n个顶点的无向图中，至少有条边，至多有条边。 24．在n个顶点的有向图中，至少有条边，至多有条边。 25．如果排序不改变之间的相对次序，则称该排序方法是稳定的。 26．如果排序改变了之间的相对次序，则称该排序方法是不稳定的。 27．当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是。 28．在一个图中，所有顶点的度数之和是所有边数的倍。 29．无向图中边的数目等于邻接矩阵中非零元素个数的倍。 30．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 31．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第二次被比较的元素是。 32．在有序表（2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第三次被比较的元素是。 三、简答题 1．对链表设置头结点的作用是什么？（至少说出两条好处） 2.写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQ ueue (Q,’h’); En Q ueue (Q,’r’); En Queue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQ ueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); }; Printf(x); } 3. 简述以下算法的功能（栈和队列的元素类型均为int ）。 void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } } 4. 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？ 5. 对以下单链表执行下列语句，简述代码的功能，并画出单链表结果示意图。 while(T->next != NULL) { T->data = 2 * T->data; T = T->next; } 6. 请画出下图的邻接矩阵和邻接表 7．假设二叉树采用顺序存储结构，如图所示。 （1）画出二叉树表示； （2）写出先序遍历、中序遍历和后序遍历的结果； （3）写出结点值c 的双亲结点，其左、右孩子； 8. 树和二叉树之间有什么样的区别与联系？ 9. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。 10. 一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求： （1）各层的结点的数目是多少？ （2）编号为n的结点的双亲结点（若存在）的编号是多少？ （3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？ （4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。 11. 如果用一个循环数组q[0..m-1]表示队列时，该队列只有一个队列头指针front，不设队列尾指针rear，而改置计数器count用以记录队列中结点的个数。 （1）编写实现队列的三个基本运算：判空、入队、出队 （2）队列中能容纳元素的最多个数是多少？ 【此题超出教学范围，不作解答。】 12. 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，画出此二叉树。并给出其后序遍历的结果。 13．假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { char data; struct node*lchild, *rchild; ∥左右孩子指针 } *BinTree； 阅读下列程序。 void f13(BinTree T){ InitStack(S); ∥初始化一个堆栈S while(T || !StackEmpty(S)){ while(T){ Push(S,T); T=T->lchild; } if(!StackEmpty(S)){ T=Pop(S); printf(“%c”,T->data); T=T->rchild; } } } 回答下列问题： (1)已知以T为根指针的二叉树如图所示，请写出执行f13(T)的输出结果： (2)简述算法f13的功能。 A B C D E F 14．设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题： （1）对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果； （2）假定二叉树B共有n个结点，试分析算法traversal(root)的时间复杂度。 二叉树B 15.已知有向图的邻接表如图所示，请回答下面问题： (1)给出该图的邻接矩阵； (2)从结点A出发，写出该图的深度优先遍历序列。 16.设要将序列{Q, H, C, Y, P, A, M, S, R, D, F, X}中的关键码按字母序的升序重新排列。简述快速排序的思 路，并以第一个元素为轴中心，给出用快速排序对序列一趟扫描的结果。 四、算法填空 1．假设线性表用不带头结点的单向链表表示，结点数据类型如下： struct node{ int s; node * next; } 下面的算法用于求线性表的长度。请在方框中填入适当的内容，将算法补充完整。 int GetLinkLen(node *h){ int s; s=0; { s=s+1; ; } return(s); } 2．设有n个顺序表元素存放在数组v[1]~v[n]中，数组v的最大下标为n0，元素类型为TElem. 下面的算法用于删除顺序表中第一个值为x的元素。请在方框中填入适当内容，将算法补充完整。 void DeleValue (TElem x){ int i, j; i=1; While( ) i=i+1; if(i<=n){ v[j-1]=v[j]; ; } 五、算法设计题 1.从顺序表中删除值为x的元素。 2.将顺序存储结构线性表（v1, v2, …, v n）改变成（vk+1,vk+2,…, vn,v1,v2,…, vk）。 3.将顺序存储的线性表（v1, v2, …, vn）改变成（v1, v3, v5,…）。 4.从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 5.从键盘输入一系列整数，建立一个长度为n的、不含重复元素的顺序表。 6.从键盘输入n个整数，建立带表头结点的单向链表。 7.设H是带表头结点的单向链表的表头指针，将链表中数值重复的结点删除。 8. 设有一带头结点的单链表，编程将链表颠倒过来。要求不用另外的数组或结点完成。 9. 统计出单链表HL中结点的值等于给定值X的结点数。 11．已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。 编写的函数具有如下原型：void func(TLinkNode *head),其中链结点的结构如下：struct TLinkNode { int data; TLinkNode *next; } 请完成该算法。 12. 编写递归算法，计算二叉树中叶子结点的数目。 数据结构 一、单选题 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．（ B ）是按照一定的数据模型组织的、长期存储在计算机内，可为多个用户共享的数据的集合。 （A）数据库系统（B）数据库 （C）关系数据库（D）数据库管理系统 2．数据库系统的基础是（ D ）。 （A）数据结构（B）数据库管理系统 （C）操作系统（D）数据模型 3．（ C ）处于数据库系统的核心位置。 （A）数据字典（B）数据库 （C）数据库管理系统（D）数据库管理员 4．对数据库的操作要以（ B ）内容为依据。 （A）数据模型（B）数据字典 （C）数据库管理系统（D）运行日志 5．在DBS中，DBMS和OS之间的关系是( B )。 （A）相互调用（B）DBMS调用OS （C）OS调用DBMS （D）并发运行 6．有了模式/内模式的映象，可以保证数据和应用程序之间的（ B ）。（A）逻辑独立性（B）物理独立性 （C）数据一致性（D）数据安全性 7．（ A ）是数据库中全部数据的逻辑结构和特征的描述。 （A）模式（B）外模式（C）内模式（D）存储模式8．（ C ）是数据库物理结构和存储方式的描述。 （A）模式（B）外模式（C）内模式（D）概念模式9．（ B ）是用户可以看见和使用的局部逻辑结构和特征的描述。（A）模式（B）外模式（C）内模式（D）概念模式10．关系操作的特点是（C ）。 （A）记录操作方式（B）字段操作方式 （C）集合操作方式（D）对象操作方式 11、用树型结构来表示实体之间联系的模型称为（B ）。 （A）关系模型（B）层次模型（C）网状模型（D）记录模型 12、数据模型中用于描述系统静态特性的是（A ）。 （A）数据结构（B）数据操作（C）完整性约束（D）数据模型13．关系中标题栏中各列的名称称为( C )。 （A）对象（B）元组（C）属性（D）记录14．在下述关系的特点中，错误的是（ D ）。 （A）列可以交换（B）行可以交换 （C）任意两元组不能相同（D）表中的数据项可分 15、下面的选项不是关系数据库基本特征的是（A ）。 （A）不同的列应有不同的数据类型（B）不同的列应有不同的列名（C）与行的次序无关（D）与列的次序无关 16、数据库系统的三级模式是指（D ）。 （A）模式、概念模式、存储模式（B）外模式、子模式、模式、（C）用户模式、子模式、存储模式（D）外模式、模式、内模式17、DBMS目前采用的数据模型中最常用的是（ D ）模型。 （A）面向对象（B）层次（C）网状（D）关系 18、下列哪一条不是由于关系模式设计不当而引起的（ B ）？ （A）数据冗余（B）丢失修改（C）插入异常（D）更新异常19、现有一个关系：借阅（书号，书名，库存数，读者号，借期，还期），假如同一本书允许一个读者多次借阅，但不能同时对一种书借多本，则该关系模式的主码是（D）。 （A）书号（B）读者号（C）书号+读者号（D）书号+读者号+借期 20．关系模式进行投影运算后（ C ）。 （A）元组个数等于投影前的元组个数 （B）元组个数小于投影前的元组个数 （C）元组个数小于或等于投影前的元组个数 （D）元组个数大于或等于投影前的元组个数 21、关系代数中的联接操作是由（B）操作组合而成。 （A）选择和投影（B）选择和笛卡尔积 （C）投影、选择、笛卡尔积（D）投影和笛卡尔积 22．在关系中，能唯一标识元组的属性集称为关系模式的（A ）。 （A）候选码（B）主码（C）外码（D）主键23．δF1(δF2(E))等价于（ C ）。 “数据结构”期末考试试题 一、单选题(每小题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、DB，DBMS和DBS三者的关系是（B） A、DB包括DBMS和DBS B、DBS包括DB和DBMS C、DBMS包括DBS和DB D、DBS与DB、DBMS无关 2、假定学生关系式S（S#，SNAME，SEX，AGE），课程关系式C（C#，CNAME，TEACHER），学生选课关系是SC（S#，C#，GRAND）。要查找选修“COMPUTER”课程的“女”学生姓名，将涉及到关系（D） A、S B、SC，C C、S，SC D、S，C，SC 3、将E-R图转换为关系模式时，如果两实体间的联系是m：n，下列说法正确的是（C） A、将m方主键（主码）和联系的属性纳入n方的属性中 B、将m方属性和n方属性中均增加一个表示级别的属性 C、增加一个关系表示联系，其中纳入m方和n方的主键（主码） D、将n方主键（主码）和联系的属性纳入m方的属性中 4、由SELECT—FROM—WHERE—GROUP—ORDER组成的SQL语句，在被DBMS处理时，各字句的执行次序为（C） A、SELECT—FROM—WHERE—GROUP—ORDER B、FROM —SELECT—WHERE—GROUP—ORDER C、FROM —WHERE—GROUP—SELECT—ORDER D、SELECT—FROM—GROUP—WHERE—ORDER 5、以下不是数据库技术所具备的特点是（D） A、数据结构化 B、数据冗余小 C、有较高的数据独立性 D、数据联系弱 6、在信息模型的“学生”尸体中，对每个学生的具体情况的描述，称为（A） A、实体值 B、实体型 C、属性值 D、属性型 7、关系数据库三级模式中的（B），可用视图实现。 A、内模式 B、外模式 C、存储模式 D、模式 8、可用于区别实体集中不同个体的属性或属性集合，称为该实体的（B） A、属性型 B、键 C、外部键 D、实体型 9、设有一个体育项目可以有多个运动员报名，一个运动员课参加多个项目，运动员与体育项目之间是（D） A、一对一的联系 B、一对多的联系 C、多对一的联系 D、多对多的联系 10、关系R与关系S只有1个公共属性，T1是R与S作等值连接的结果，T2是R与S作自然连接的结果，则（D） A、T1的属性个数等于T2的属性个数 B、T1的属性个数小于T2的属性个数 C、T1的属性个数大于或等于T2的属性个数 D、T1的属性个数大于T2的属性个数 11、数据库系统是由应用程序、DBMS、DB以及DBA组成。其中核心部分是（C） A、应用程序 B、DBA C、DBMS D、DB 12、下列集函数中不忽略空值（NULL）的是（A） A、COUNT（*） B、MAX（列名） C、SUM（列名） D、A VG（列名） 13、一个关系中的候选关键字（B） A、至少一个 B、可多个 C、必须多个 D、至少3个 14、在数据库设计中，具有最小性、唯一性和非空性的是（B） A、索引 B、关系模型主关键字（主码） C、外关键字（外码） D、约束 15、常用的关系运算时关系代数和（C） A、集合代数 B、逻辑演算 C、关系演算 D、集合演算 16、在基本层次联系中，记录型之间的联系是（B） A、一对一联系 B、一对多联系 C、多对多联系 D、多对一联系 17、关于冗余数据的叙述中，不正确的是（C） A、冗余的存在容易破坏数据库的完整性 B、冗余的存在给数据库的维护增加困难 C、不应该在数据库中存储任何冗余数据 D、冗余数据是指可由基本数据导出的数据 18、五种基本关系代数运算分别（D） A、∪、∩、∞、π、σ B、∪、-、∞、π、σ C、∪、∩、×、π、σ D、∪、-、×、π、σ 南阳理工学院2013-2014学年第2学期试卷（A卷） 课程：《数据结构》课程号：1504108130 考核方式：（闭卷）课程性质：专业必修课适用对象：12级软件工程专业 题号一二三四五总分复核人 满分20 20 10 30 20 100 得分 评卷人得分 一、选择题：（每题2 分，共20 分） 1.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06， 07，08，09}，R={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是（）。 A.线性结构 B.树型结构 C.物理结构 D.图型结构 2.栈和队列的共同特点是（）。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是（）。 A.p->next->next==head B.p->next==head C.p->next->next==NULL D.p->next==NULL 4.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。 A.s->next=p+1; p->next=s; B.(*p).next=s; (*s).next=(*p).next; C.s->next=p->next; p->next=s->next; D.s->next=p->next; p->next=s; 5.数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾 元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为 （）。 A.r-f B.(n+f-r)%n C.n+r-f D.（n+r-f)%n 6.设有数组A[0..7][0..9]，数组的每个元素长度为2字节，数组从内存首地址 1000开始顺序存放，当用以行为主存放时，元素A[5][8]的存储首地址为（）。 A.1116 B.1094 C.1138 D.1120 7.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上 所有元素)依次存放于一维数组B[1..n(n+1)/2]中，则在B中确定a ij（i 数据结构试题样题及答案 一、单项选择题（每小题2分，共30分） 1.数据结构中，与所使用的计算机无关的是数据的（）结构。 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 2.下述各类表中可以随机访问的是（）。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（）。 A. 21 B. 20 C. 19 D. 25 4.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（）。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5.一个队列的入队序列是5，6，7，8，则队列的输出序列是（）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 6. 串函数StrCmp（“d”，“D”）的值为（）。 A．0 B．1 C．-1 D．3 7．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 A．p=q→next B．p→next=q C．p→next=q→next D．q→next=NULL 8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 9.对如图1所示二叉树进行中序遍历，结果是（）。 A. dfebagc B. defbagc C. defbacg D.dbaefcg 图1 10 . 任何一个无向连通图的最小生成树（）。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 11．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。 A．33 B．32 C．85 D．41 12 .一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。 A．31，29，37，85，47，70 B．29，31，37，47，70，85 数据库原理 第一章 1. 单个用户使用的数据视图的描述称为（A）(2001年10月全国卷) A. 外模式 B. 概念模式 C. 内模式 D. 存储模式 2. 子模式DDL用来描述（B）(2001年10月全国卷) A. 数据库的总体逻辑结构 B. 数据库的局部逻辑结构 C. 数据库的物理存储结构 D. 数据库的概念结构 3. 在DBS中，DBMS和OS之间的关系是（B）(2001年10月全国卷) A. 相互调用 B. DBMS调用OS C. OS调用DBMS D. 并发运行 4.数据库物理存储方式的描述称为( B)(2003年1月全国卷) A.外模式 B.内模式 C.概念模式 D.逻辑模式 5.在下面给出的内容中，不属于DBA职责的是( C)(2003年1月全国卷) A.定义概念模式 B.修改模式结构 C.编写应用程序 D.编写完整性规则 6.在数据库三级模式间引入二级映象的主要作用是(A )(2003年1月全国卷) A.提高数据与程序的独立性 B.提高数据与程序的安全性 C.保持数据与程序的一致性 D.提高数据与程序的可移植性 、DBMS和DBS三者之间的关系是( B)(2003年1月全国卷) 包括DBMS和DBS 包括DB和DBMS 包括DB和DBS D.不能相互包括 中“第三级存储器”是指( B)(2002年10月全国卷) A.磁盘和磁带 B.磁带和光盘 C.光盘和磁盘 D.快闪存和磁盘 9.位于用户和操作系统之间的一层数据管理软件是（C） 10.数据库系统中的数据模型通常由（A）三部分组成 A、数据结构、数据操作和完整性约束 B、数据定义、数据操作和安全性约束 C、数据结构、数据管理和数据保护 D、数据定义、数据管理和运行控制 12.数据库技术的三级模式中，数据的全局逻辑结构用（C）来描述 A、子模式 B、用户模式 C、模式 D、存储模式 13.用户涉及的逻辑结构用（D）描述 《数据结构》期末考试试卷样卷 成绩＿＿＿＿＿＿＿＿ 一、单项选择题：（每题2分，共30分） 1、以下说法正确的是（）。 A. 数据元素是数据的最小单位 B. 数据项是数据的基本单位 C. 数据结构是带有结构的各数据项的集合 D. 一些表面上很不相同的数据可以有相同的逻辑结构 2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A. 存储结构 B. 存储实现 C. 逻辑结构 D. 运算实现 3、判断一个队列QU（最多元素为m0）为满队的条件是（）。 A. QU->rear-QU->front==m0 B. QU->rear-QU->front-1==m0 C. QU->rear==QU->front D. QU->front==QU->rear+1 4、给定n个数据元素，建立对应的有序单链表的时间复杂度是（）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 5、一个非空广义表的表头（）。 A. 不可能是子表 B. 只能是子表 C. 原子或子表均可 D. 只能是原子 6、设完全二叉树中拥有65 个结点，则其深度为（）。 A. 5 B. 6 C. 7 D. 8 7、根据二叉树的（），可以唯一确定该二叉树的形态。 A. 先序和中序序列 B. 先序和后序序列 C. 中序和后序序列 D. 先序和层序序列 8、若广义表A满足Head(A)=Tail(A)，则A为（）。 A. () B. (()) C. ((),()) D. ((),(),()) 9、下面不正确的说法是（）。 (1)在AOE网中，减少任一关键活动上的权值后，整个工期也就相应减小； (2)AOE网工程的工期为关键活动上的权值之和； (3)在关键路径上的活动都是关键活动，而关键活动也必定在关键路径上。 A. (1) B. (2) C. (3) D. (1) 、(2) 10、图的深度优先遍历算法分别类似于二叉树的（）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 11、从图的邻接矩阵中，容易确定（）。 A. 主对角线的元素全部为1 B. 主对角线的元素不全为0 C. 任意两个顶点之间是否关联 D. 是否为一个连通图 12、顺序查找适用于存储结构为（）的线性表。 A. 散列存储 B. 压缩存储 C. 顺序存储或链式存储 D. 索引存储 13、从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为（）。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 14、在关键字随机分布的情况下，用二叉排序树进行查找，其查找长度与（）量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 均不是 15、一组记录的关键字序列为{46,79,56,38,40,84}，利用快速排序方法，以第一个记录为基准得到的一次划分是（）。 A. 38,40,46,56,79,84 B. 40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79 - 1 - 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 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. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 一、选择题（每题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. 投影、选取、笛卡尔乘积、差运算 哈尔滨工业大学 二〇〇八年硕士研究生考试模拟试题（一） 考试科目：计算机专业基础 适用专业：计算机科学与技术 I 数据结构（含高级语言）部分（共75分） 一、填空题（每空1分，共9分） +?++的后缀表达式 1.表达式23((12*32)/434*5/7)108/9 是。 2.设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为。 3.设有广义表A=（（（a，b），x），（（a），（b）），（c，（d，（y）））），得到y的对广义表 A的操作序列为。 4.如果二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总节点数 为。 5.G是一个非连通无向图，共有28条边，则该图至少有个顶点。 6.构造n个结点的强联通图，至少有条弧。 7.设表长为1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查 找成功的ASL是。 8.分别采用堆排序、快速排序、冒泡排序和归并排序，对初太为有序的表，则最省时 间的是算法，最费时间的是算法。 二、单项选择题（每题1分，共11分） 1.静态链表中指针表示的是（） A 下一元素的地址 B 内存储器的地址 C 下一元素在数组中的位置 D 左链或右链指向的元素的地址 2.计算算法的时间复杂度是属于一种（） A 事前统计的方法 B 事前分析估算的方法 C 事后统计的方法 D 时候分析估算的方法 3.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3， 当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（） A 1和5 B 2和4 C 4和2 D 5和1 4.若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储 单元，则第3行第4列的元素（假定无第0行第0列）的地址是（） A 1040 B 1042 C 1026 D 都不正确 5.一棵124个叶节点的完全二叉树，最多有（）个节点。 数据结构期末考试题及标准答案 ————————————————————————————————作者：————————————————————————————————日期： 2012年数据结构期末考试题及答案 一、选择题 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＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 《数据库技术》复习题 一、选择题 1.数据库系统与文件系统的主要区别是 B 。 A.数据库系统复杂，而文件系统简单； B.文件系统不能解决数据冗余和数据独立性问题，而数据库系统可以解决； C.文件系统只能管理程序文件，而数据库系统可以管理各类文件； D.文件系统管理的数据量较少，而数据库系统可以管理庞大的数据量。 2.网状模型的数据结构是 D 。 A．线性表B．二维表C．树D．有向图 3.在层次模型中，记录之间的联系通过 A 来实现。 A．指针B．数组C．公共属性D．对象标识 4.数据库系统三级结构的描述放在 D 中。 A．用户数据库B．运行日志 C．数据库管理系统D．数据字典 5.数据独立性是指 B 之间相互独立，不受影响 A．概念数据模型和逻辑数据模型 B．应用程序和数据库的数据结构 C．概念数据模型与数据库的数据结构 D．数据与数据库的数据结构 6.在数据库的三级体系结构中，外模式/逻辑模式映象可以保证数据结构和应用程 序之间的 A 。 A．逻辑独立性B．物理独立性 C．数据一致性D．数据安全性 7.关系数据库中，实现实体之间的联系是通过表与表之间的 D 进行。 A. 公共索引. B.公共存储. C.公共元组. D.公共属性 8.主键的属性上有空值违反了 A 。 A．实体完整性规则B．参照完整性规则 C．安全性规则D．模型转换规则 9.参照完整性规则是对 D 的约束。 A．超键B．候选键C．主键D．外键 10.设关系R，按条件f对关系R进行选择，其关系代数是___C___。 A. σf（R×R） B. Πf（R∞R） C. σf(R) D. Πf(R) 11.数据模型的三要素是___A___。 A. 数据结构、数据操作和数据完整性 B. 数据结构、数据库定义和数据库维护 C. 数据定义、数据操作和数据维护 D. 关系数据库、层次数据库和网状数据库 12.设关系R和S的元数分别是r和s，则R和S笛卡儿积的元数是 A 。 A．r*s B．r+s C．r-s D．r/s 13.在SELECT语句中使用“*”表示 C 。 数据结构试题（A05） 一、选择题（共10小题，每小题1分，共10分） 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m=m+1； A. O(n2) B.O(m+n+1) C.O(m+n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个元素需要移动的元素的平均个数为( ) A.n/2 B.（n-1）/ 2 C.(n+1)/2 D.(n+2)/2 4.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 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.（100，85，40，77，80，60，66，98，82，10，20） D.（10，20，40，60，66，77，80，82，85，98，100） 8．在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 二、填空题（共20小题，每小题1分，共20分） 1、在单链表中，删除指针P所指结点的后继结点的语句是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8，1….8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） 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） 9.对一组数据（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则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 (说明:仅仅代表个人观点，答案正确率为９8%，可能会有错的地方，有问题请问度娘) 复习参考资料 选择题:3０分（15题) 名词解释：２０分(4题） 综合题：5０分 一、选择题: 1．数据库系统是采用了数据库技术的计算机系统,数据库系统由数据库、数据库管理系统、应用系统和（C）。 Ａ. 系统分析员 Ｂ．程序员 C. 数据库管理员 D. 操作员 2. 数据库（DＢ),数据库系统（DBS)和数据库管理系统(ＤＢMS)之间的关系是( Ａ)。 Ａ. DBS包括DＢ和DBＭＳ B．DBMＳ包括ＤB和ＤBS Ｃ. DB包括ＤBS和DBMS D.DBS就是DB，也就是DBMＳ 3. 下面列出的数据库管理技术发展的三个阶段中,没有专门的软件对数据进行管理的是( D）。Ｉ．人工管理阶段II.文件系统阶段ＩII．数据库阶段 A. I和II Ｂ.只有II C. II和III Ｄ. 只有Ｉ 4. 下列四项中,不属于数据库系统特点的是（C ）。 A．数据共享 Ｂ. 数据完整性 C．数据冗余度高 D.数据独立性高 5. 数据库系统的数据独立性体现在（B)。 A. 不会因为数据的变化而影响到应用程序 B. 不会因为数据存储结构与数据逻辑结构的变化而影响应用程序 C．不会因为存储策略的变化而影响存储结构 D．不会因为某些存储结构的变化而影响其他的存储结构 6．描述数据库全体数据的全局逻辑结构和特性的是（Ａ）。 A. 模式 B. 内模式 Ｃ．外模式 Ｄ. 以上三种 7.要保证数据库的数据独立性,需要修改的是（Ｃ)。 A. 模式与外模式 B.模式与内模式 C．三级模式之间的两层映射 D. 三层模式 8. 要保证数据库的逻辑数据独立性，需要修改的是( A)。 Ａ. 模式与外模式之间的映射 B. 模式与内模式之间的映射 C. 模式 D.三级模式 9．用户或应用程序看到的那部分局部逻辑结构和特征的描述是( C)模式。 A. 模式 Ｂ. 物理模式 C．子模式 D．内模式 10. 下述（D）不是DBA数据库管理员的职责。 A. 完整性约束说明 B．定义数据库模式 C. 数据库安全 D. 数据库管理系统设计 １1．概念模型是现实世界的第一层抽象,这一类模型中最著名的模型是（Ｄ）。A．层次模型 B. 关系模型 C. 网状模型 D．实体-关系模型 1２．区分不同实体的依据是（B）。 Ａ.名称 B．属性 C.对象 Ｄ.概念 13. 关系数据模型是目前最重要的一种数据模型，它的三个要素分别是（B )。Ａ．实体完整性、参照完整性、用户自定义完整性 B. 数据结构、关系操作、完整性约束 C. 数据增加、数据修改、数据查询 D．外模式、模式、内模式 １４．在(A ）中一个结点可以有多个双亲,结点之间可以有多种联系。 A.网状模型 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 。 A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 2. 下述函数中对应的渐进时间复杂度（n 为问题规模）最小是 。 (n)=nlog 2n+5000n (n)=n 2 -8000n (n)= n n 2 log -6000n (n)=7000log 2n 3. 设线性表有n 个元素，以下操作中， 在顺序表上实现比在链表上实现效率更高。 A.输出第i （1≤i ≤n ）个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n 个元素的值 D.输出与给定值x 相等的元素在线性表中的序号 4. 设n 个元素进栈序列是p 1，p 2，p 3，…，p n ，其输出序列是1，2，3，…，n ，若p 3=3，则p 1的值 。 A.可能是2 B.一定是2 C.不可能是1 D.一定是1 5. 以下各种存储结构中，最适合用作链队的链表是 。 A.带队首指针和队尾指针的循环单链表 B.带队首指针和队尾指针的非循环单链表 C.只带队首指针的非循环单链表 D.只带队首指针的循环单链表 6. 对于链串s （长度为n ，每个结点存储一个字符），查找元素值为ch 的算法的时间复杂度为 。 (1) (n) (n 2) D.以上都不对 7. 设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是 。 8. 一个具有1025个结点的二叉树的高h 为 。 ～1025 ～1024 9. 一棵二叉树的后序遍历序列为DABEC ，中序遍历序列为DEBAC ，则先序遍历序列为 。 10. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列 。数据结构考试试题及答案
2014-1-数据库复习题-答案
数据结构C语言版期末考试试题(有答案)
数据库复习题答案
2014(1)数据结构-A-试题
数据结构试题样题及答案
大学数据库复习题及答案整理
数据结构期末考试试卷样卷
2017年数据结构期末考试题及答案A
数据库期末考试试题及答案
数据结构研究生入学考试模拟题(一)
数据结构期末考试题及标准答案
2014-15--数据库期末复习题(有答案)
数据结构模拟题及答案
《数据结构》期末考试题及答案
数据库复习题答案
数据结构考试题
相关主题
文本预览