7数据结构复习题
一、填空题
(1)若已知一个栈的输入序列为1 ,2, 3 ,...n ,其输出序列为p1,p2,p3,....pn。若p1=n,则pi
为n-i+1。
(2) 在单循环链表中，指针p 所指结点为最后一个结点的条件是p->link==first。
(3)具有32有结点的完全二叉树的深度为 6 。
(4) L是带有头结点的单链表的头指针,第一个元素结点的指针是 first 。
(5)从逻辑关系上讲,数据结构主要分为两大类,它们是线性结构和非线性结构。
(6)有序表中元素为1，2，3，4，5，6，7，8，9.11采用二分查找方法进行查找，共有 2 个元素的查找长度为2。
(7)从无向图中的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。
(8)归并排序的时间复杂性为O(nlog2n)。
(9) 在一个长度为n的顺序表中删除第m个元素时，需向前移动n-m个元素。
(10) 多维数组实际上是由__一维数组的扩展实现的。
(11) 链接存储的特点是利用__指针___来表示数据元素之间的逻辑关系。
(12) 后缀表达式“4 5 * 3 2 + -”的值为__ 15______。
(14) 一个算法的复杂性可分为_ 时间 ___复杂性和空间复杂性。
(16) 在一棵树中，叶结点没有后继结点。
(17)
(18) 在单链表中，指针p 所指结点为最后一个结点的条件是p->next=NULL。
(19) 栈是一种限定在表的一端进行插入和删除的线性表，又被称为后进先出的线性表。
(20) 设图G=(V,E)，V={1,2,3,4}, E={<1,2>,<1,3>,<2,4>,<3,4>，<2,3>}，从顶点1出发，对图G进行广度优先搜索的序列有___2 __种。
(21)已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有_____ 12_______ 个叶子的结点。n0=n2+2n3+1
(22) 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next; _____p->next = s___________;。
(23) 在无向图的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于__ 1 ______。
(24)
(25) 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为____s->left_____=p；s->right=p->right；__p->right______=s；
p->right->left=s；（设结点中的两个指针域分别为left和right）。
(26)已知一个有序表为（13，35，47，50，62，83，90，115，134），当二分检索值为90的
元素时，需 2 次比较可检索成功。
(27) 设表中元素的初始状态是无序的，分别用堆排序、快速排序、冒泡排序和归并排序方
法对其进行（按递增排序），快速排序最费时间。
(29) 设一组初始记录关键字序列为(20，18，15，16，30，19)，则以20为中轴的一趟快
速排序结果为_____ ___ __。
(30)数据结构的存储结构包括顺序、链接、__ 索引 _和散列等四种。
(32) 在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的
效率高。
(33) 设有顺序栈s[0..m-1]，若栈底设在下标最小的一端，则栈满的条件是
（设栈顶指针为top，指向栈顶元素的位置）。top==m-1
(34) 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是__ 递归 _
_的对象。
(35) 若对一棵二叉树的结点编号从0开始顺序编码，按顺序存储，把编号为0的结点存储
到a[0]中，其余类推，则a[i]元素的左孩子元素为__ a[2i+1] ____
__。
(36) 中缀表达式(A+B)*D+E/(F+A*D)+C所对应的后缀表达式为__ ____
__。
二、单项选择题
（1）有下面的算法段：for (i=0; i A．O(1) B．O(n) C．O(log2n) D．O(n2) （2）以下关于数据结构的说法，正确的是（）。 A. 数据结构的逻辑结构独立于其存储结构 B. 数据结构的存储结构独立于该数据结构的逻辑结构 C. 数据结构的逻辑结构唯一地决定了该数据结构的存储结构 D. 数据结构仅由其逻辑结构和存储结构决定 （3）设有一个n n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0] 存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（ C ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 （4）若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（） 存储方式最节省时间。 A. 单链表 B. 双链表 C. 单向循环 D. 顺序表 （5）假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL （6）在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于( )。 A. 2h-1 B. 2h+1 C. 2h-1 D. 2h （7）（）二叉排序树可以得到一个从小到大的有序序列。 A．先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 (8) 设有两个串s1和s2。求s2在s1中首次出现的位置的操作称为（ B ）。 A．连接B．模式匹配C．求子串D．求串长 (9) 往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动（）个结点。 A．n B．n/2 C．n+1 D．(n+1)/2 (10) 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（）。 A. O(1) B. O(m) C. O(n) D. O(m+n) (11) 一个栈的元素进栈序列是a、b、c、d、e，那么下面的（）不能做为一个出栈序列。 A．e、d、c、b、a B．d、e、c、b、a C．d、c、e、a、b D．a、b、c、d、e (12)将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。结点编号为49的父结点的编号为（）。 A. 24 B. 25 C. 23 D. 无法确定 (13)深度为6（根的层次为1）的二叉树至多有（）结点。 A. 64 B. 32 C. 31 D. 63 (14)设有一个无向图G=（V，E）和G’=（V’，E’）如果G’为G的生成树，则下面不正确的说法是（）。 A. G’为G 的子图 B. G’为G 的边通分量 C. G’为G的极小连通子图且V’=V D. G’为G的一个无环子图 (15)以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是 ( A )。 A．集合中任何两个结点之间都有逻辑关系但组织形式松散 B．线性结构中结点按逻辑关系依次排列形成一条"锁链" C．树形结构具有分支、层次特性，其形态有点像自然界中的树 D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 (16) 若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A. 指针 B. 引用 C. 传值 D. 常值 (17)在长度为n的顺序表的第i (1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A．n-i+1 B. n-i C. i D. i-1 (18)对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A．顺序表 B．用头指针表示的单循环链表 C．用尾指针表示的单循环链表 D．单链表 (19)一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（） A．e d c b a B．d e c b a C．d c e a b D．a b c d e (20)n个顶点的有向图中含有向边的数目最多为 ( ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) (21)已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为( )。 A．4 B．5 C．6 D．7 (22)已知图1如右所示，若从顶点A出发按深度优先搜索进行遍历，则可能得到的顶点序列为（）。 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 (23) 以下说法错误的是（）。 A、抽象数据类型具有封装性。 B、抽象数据类型具有信息隐蔽性。 C、使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D、抽象数据类型的一个特点是使用与实现分离。 （24）在计算递归函数时,如不使用递归过程,则一般情况下必须借助于( )数据结构。 A、队列 B、广义表 C、二叉树 D、栈 (25)非空的单循环链表L的尾结点p满足条件为 ( ) 。 A、p->next==null B、p==null C、p->next==L D、 p==L (26) 树最适合用来表示 ( ) 。 A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 (27)如果以链表作为栈的存储结构，则退栈操作时（） A、必须判别栈是否满 B、对栈不作任何判别 C、必须判别栈是否空 D、判别栈元素的类型 (28）如果只想到1024个元素组成的序列中前5个最小元素，那么用（）方法最快。 A、起泡排序 B、快速排序 C、堆排序 D、直接选择排序 (29)一个具有n个顶点的无向图中，要连通全部顶点至少需要( ) 条边。 A 、n B 、n+1 C 、n/2 D 、n-1 (30)已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，该树的深度为( )。 A 、4 B 、5 C 、6 D 、7 (31) 若各元素的逻辑顺序与其存放的物理顺序一致，则称这种存储结构为( ) A 、顺序存储结构 B 、链式存储结构 C 、索引存储结构 D 、散列存储结构 (32)一个队列的输入序列是a d c b ，则队列的输出序列是 ( ) 。 A 、 a d c b B 、b c d a C 、d c b a D 、 c b a d (33)有32个结点的完全二叉树的深度为 ( ) （根的层次为1）。 A 、8 B 、7 C 、6 D 、5 (34)一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列是 （ ） 。 A 、2 3 4 1 5 B 、5 4 2 3 1 C 、2 3 1 4 5 D 、 1 5 4 3 2 (35) 设键字序列为3,7,6,9,8,1,4,5,2,则对它们进行排序的最小交换次数是（ ）。 A 、8 B 、7 C 、6 D 、9 (用简单选择排序，正好是交换6次) (36)栈操作的原则是 （ ）。 A 、先进先出 B 、后进先出 C 、只能进行插入 D 、只能进行删除 (37)下列四种排序中（ ）的空间复杂度最大。 A 、 快速排序 B 、 冒泡排序 C 、 希尔排序 D 、 堆 (38) 向具有n 个结点的、结构均衡的二叉搜索树中删除一个元素的时间复杂度大致为 ( )。 A 、O(1) B 、 O(log 2n ) C 、O(n) D 、O(nlog 2n) 三、 判断题 (1)数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 （ × ） (2)顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ √ ） (3) 串的长度是串中所含字母的个数n （n ≧0）。（ X ） (4)由树转化成二叉树，该二叉树的右子树不一定为空 。（ × ） (5)链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。（ × ） (6)线性表中的所有元素都有一个前驱元素和后继元素。（ × ） (7)完全二叉树中的叶子结点只可能在最后两层中出现。（ √） （8）数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（ √ ） （9）具有n 个结点的完全二叉树的高度为2log 1n +????。 （ √ ） （10）数组是一种静态的存储空间分配,就是说,在程序设计时必须预先定义数组的数据类型和存储空间大小,由编译程序在编译时进行分配. （ × ） （11）设有80个元素有序排列，用二分折半检索法检索时，最少比较次数是2，最大比较次数为 10 。（×） （12）对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( × ) （13）顺序表用一维数组作为存储结构，因此顺序表是一维数组。（×） （14）在平衡二叉树中，任意结点左右子树的高度差(绝对值）不超过1。（√ ) （15）数组元素的下标值越大，存取时间越长。( × ) （16）链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生存储溢出的问题。（√） （17）顺序表和一维数组一样，都可以按下标随机（或直接）访问。（√）（18）对无序表用二分法查找比顺序查找快。（×）二分法不能应用于无序表（19）快速排序总比其它排序快。（×） （20）如果有向图中各个顶点的度都大于2,则该图中必有回路. （√） （21）若一棵二叉树中的结点均无右孩子，则该二叉树的中序遍历和后序遍历序列正好相反。（×） (22) 凡是递归定义的数据结构都可以用递归算法来实现它的操作。（√） (22) 二维数组和多维数组均不是特殊的线性结构。（×） (23)向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（×） (24)如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（√） (25)非空的双向循环链表中任何结点的前驱指针均不为空。（√） (26)“顺序查找法”是指在顺序表上进行查找的方法。（×） (27)对链表进行插入和删除操作时，不必移动结点。（√） (28) 栈可以作为实现程序设计语言过程调用时的一种数据结构。（√） (31)顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（×） (32) 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√） (33) 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。（×）前一个位置 (34) 用非递归方法实现递归算法时一定要使用递归工作栈。（） (35)具有12个结点的完全二叉树有5个度为2的结点。（√） (36) 如果有向图中各个顶点的度都大于2,则该图中必有回路. （×） (37) 在哈夫曼树中，权值最小的结点离根结点最近。( × ) (38) 对具有n个元素的待排序序列进行归并排序时，需归并的趟数为[㏒2n]。（√） 四、分析题 （1）．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG，画出该二叉树。（ 后续遍历就是ABCDEFGH （2）已知带权图如下所示，给出使用Kruskal算法构造最小生成树的过程。 （3）以数据集（67，9，2，34，3，24，10）为叶结点的权值，构造一棵哈夫曼树。 （4）给定一个随机排列的数据序列{12,67,80,44,39,58,31}，请写出直接插入排序前三趟排序结果。 (5) 对关键字序列(98，20，12，75，29，61，36，87) 进行堆排序，使之按关键字递增次序排列，请写出排序过程中建初始堆的过程。 (6) 将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） (7)对下图所示的树，分别用前序、中序和后序遍历方法进行遍历，并写出每种遍历所得到的结点访问序列。 （8）设无向图G（如下图所示），给出该图的最小生成树上边的集合并计算最小生成树各边 上的权值之和。 （9）设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是SA，每个数组元素占5个存储字，求A[6][7]的存储字地址是多少。 五、算法设计题 （1）设有一个表头为first的单链表。根据单链表的结构定义试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。 typedef struct node { //链表结点 ElemType data; //结点数据域 struct node * link; //结点链域 } ListNode， * LinkList; (2)给定两维数组A[m][n], 假定m=n，设计一个算法，计算正、反两条对角线上的元素的和。int sum3(int A[m][n] ,int n){ (3) 写出求一棵二叉树的叶子结点数量的算法。 int BinTreeLeaf(BitTree T){ (4)设某单链表Ｌ的结点结构为 的，若递增返回1，别的返回0。 Int isviser(lklist L) （5）写出求一棵二叉树的结点总数的算法。 int BinTreeCOUNT(BitTree T){ 数据结构 一、单选题 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--数据库期末复习题(有答案)
数据结构模拟题及答案
《数据结构》期末考试题及答案
数据库复习题答案
数据结构考试题
相关主题
文本预览