下载文档原格式
数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。
2.___栈__又称为LIFO表。
3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。
4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。
5.在串S=“structure”中，以r为首字符的子串有_9_个。
6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。
7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。
8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。
9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。
10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。
11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。
12.一棵深度为5的满二叉树中的结点数为_______31_______个。
13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。
14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。
15._____拓朴排序______可以判断出一个有向图中是否有环。
计算机系统结构自考真题及答案解析（一）总分：140分题量：55题一、单选题（共39题，共78分）1.IBM370系统将中断的类型分为（）A.3类B.4类C.5类D.6类正确答案：D本题解析：暂无解析2.下列属于总线标准的是（）A.电气B.速率C.流量D.吞吐率正确答案：A本题解析：暂无解析3.为了解决主存的容量满足不了要求，采用的技术是（）A.寄存器B.虚拟存储器C.高速缓存D.控制存储器正确答案：B本题解析：暂无解析4.标量流水处理机的性能指标主要有（）A.吞吐率、加速比、时间延迟B.吞吐率、效率、时间延迟C.吞吐率、加速比、效率D.加速比、效率、时间延迟正确答案：C本题解析：暂无解析5.多处理机属于（）A.SISD系统B.SIMD系统C.MISD系统D.MIMD系统正确答案：D本题解析：暂无解析6.在计算机系统多级层次结构中,机器级从低级到高级，相对顺序正确的是()。
A.汇编语言——操作系统——高级语言B.微程序一传统机器语言一汇编语言C.传统机器语言——高级语言——汇编语言D.汇编语言——应用语言——高级语言正确答案：B本题解析：暂无解析7.下列对系统程序员不透明的是()。
A.Cache存储器B.数据通路宽度C.指令缓冲寄存器D.虚拟存储器正确答案：D本题解析：暂无解析8.下列予寻址方式的三种面向的是()。
A.面向主存B.面向辅存C.面向寄存器D.面向堆栈正确答案：B本题解析：暂无解析9.浮点数尾数的基值rm=-8，尾数的计算机位数m=8位，可表示的尾数的个数为()。
A.23×7B.24×7C.25×7D.26×7正确答案：C本题解析：暂无解析10.IBM370系统中，通道动作故障引起的中断属于()。
A.机器校验中断B.访管中断C.程序性中断D.I/O中断正确答案：A本题解析：暂无解析11.程序员编写程序时使用的地址是()。
A.主存地址B.逻辑地址C.物理地址D.有效地址正确答案：B本题解析：暂无解析12.对指令间“一次重叠”描述不正确的是()。
数据结构试题（含答案）⼀、单选题（每题 2 分，共20分）1. 1.对⼀个算法的评价，不包括如下（B ）⽅⾯的内容。
A．健壮性和可读性B．并⾏性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插⼊⼀个由指针p指向的结点，则执⾏( )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采⽤链表表⽰？( )A.经常需要随机地存取元素B.经常需要进⾏插⼊和删除操作C.表中元素需要占据⼀⽚连续的存储空间D.表中元素的个数不变4. 4.⼀个栈的输⼊序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV⽹是⼀种（）。
A．有向图B．⽆向图C．⽆向⽆环图D．有向⽆环图6. 6.采⽤开放定址法处理散列表的冲突时，其平均查找长度（）。
A．低于链接法处理冲突 B. ⾼于链接法处理冲突C．与链接法处理冲突相同D．⾼于⼆分查找7.7.若需要利⽤形参直接访问实参时，应将形参变量说明为（）参数。
A．值B．函数C．指针D．引⽤8.8.在稀疏矩阵的带⾏指针向量的链接存储中，每个单链表中的结点都具有相同的（）。
A．⾏号B．列号C．元素值D．⾮零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。
A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)B. O(1)C. O(log2n)D. O(n2)⼆、⼆、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
全国计算机等级考试二级笔试试卷公共基础知识及C++语言程序设计(考试时间90分钟，满分100)分)一、选择题((1)～(35)每小题2分，共70分)下列各题A)、B)、C)、D)四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上，答在试卷上不得分。
(1) 下面叙述正确的是A)算法的执行效率与数据的存储结构无关B)算法的空间复杂度是指算法程序中指令(或语句)的条数C)算法的有穷性是指算法必须能在执行有限个步骤之后终止D)以上三种描述都不对(2)以下数据结构中不属于线性数据结构的是A)队列 B)线性表 C)二叉树 D)栈(3)在一棵二叉树上第5层的结点数最多是A)8 B)16 C)32 D)15(4)下面描述中，符合结构化程序设计风格的是A)使用顺序、选择和重复(循环)三种基本控制结构表示程序的控制逻辑B)模块只有一个入口，可以有多个出口C)注重提高程序的执行效率D)不使用goto语句(5)下面概念中，不属于面向对象方法的是A)对象 B)继承 C)类 D)过程调用(6)在结构化方法中，用数据流程图(DFD)作为描述工具的软件开发阶段是A)可行性分析 B)需求分析 C)详细设计 D)程序编码(7)在软件开发中，下面任务不属于设计阶段的是A)数据结构设计 B)给出系统模块结构C)定义模块算法 D)定义需求并建立系统模型(8)数据库系统的核心是A)数据模型 C)软件工具B)数据库管理系统 D)数据库(9)下列叙述中正确的是A)数据库系统是一个独立的系统，不需要操作系统的支持B)数据库设计是指设计数据库管理系统C)数据库技术的根本目标是要解决数据共享的问题D)数据库系统中，数据的物理结构必须与逻辑结构一致(10)下列模式中，能够给出数据库物理存储结构与物理存取方法的是A)内模式 B)外模式 C)概念模式 D)逻辑模式(11)关于面向对象的程序设计方法，下列说法正确的是A)“封装性”指的是将不同类型的相关数据组合在一起，作为一个整体进行处理B)“多态性”指的是对象的状态会根据运行时要求自动变化C)基类的私有成员在派生类的对象中不可访问，也不占内存空间D)在面向对象的程序设计中，结构化程序设计方法仍有着重要作用(12)判断字符型变量ch是否为大写英文字母，应使用表达式A ) ch>='A' & ch<='Z'B ) ch<='A' ||ch>='Z'C ) 'A'<=ch<='Z'D ) ch>='A' && ch<='Z'(13)已知下列语句中的x和y都是int型变量，其中错误的语句A ) x=y++;B ) x=++y;C ) (x+y)++;D ) ++x=y;(14)执行语句序列int n;cin >> n;switch(n){ case 1:case 2: cout << '1';case 3:case 4: cout << '2'; break;default: cout << '3';}时，若键盘输入1，则屏幕显示A)1 B)2 C)3 D)12(15)下列程序的输出结果是#include <iostream>using namespace std;int main(){char a[] = "Hello, World";char *ptr = a;while (*ptr){if (*ptr >= 'a' && *ptr <= 'z')cout << char(*ptr + 'A' -'a'); else cout << *ptr;ptr++;}return 0;}A ) HELLO, WORLDB ) Hello, WorldC ) hELLO, wORLD D ) hello, world(16)已知：int m=10；在下列定义引用的语句中，正确的是A ) int &x=m;B )int y=&m;C )int &z;D ) int &t=&m;(17)下列函数原型声明中错误的是A ) void Fun(int x=0, int y=0);B ) void Fun(int x, int y);C ) void Fun(int x, int y=0);D ) void Fun(int x=0, int y);(18)已知程序中已经定义了函数test，其原型是int test(int, int, int);，则下列重载形式中正确的是A ) char test(int,int,int);B ) double test(int,int,double);C ) int test(int,int,int=0);D ) float test(int,int,float=3.5F);(19)有以下程序#include<iostream>int i = 0;void fun(){ {static int i = 1;std::cout<<i++<<',';}std::cout<<i<<',';}int main(){fun(); fun();return 0;}程序执行后的输出结果是A)1,2,1,2, B)1,2,2,3, C)2,0,3,0,D)1,0,2,0,(20)已知函数f的原型是：void f(int *a, long &b); 变量v1、v2的定义是：int v1;long v2;，正确的调用语句是A) f(v1, &v2); B) f(v1, v2);C) f(&v1, v2); D) f(&v1, &v2);(21)有以下类定义class MyClass{public:MyClass(){cout<<1;}};则执行语句MyClass a, b[2], *p[2];后，程序的输出结果是A)11 B)111 C)1111 D)11111(22)关于友元，下列说法错误的是A)如果类A是类B的友元，那么类B也是类A的友元B)如果函数fun()被说明为类A的友元，那么在fun()中可以访问类A的私有成员C)友元关系不能被继承D)如果类A是类B的友元，那么类A的所有成员函数都是类B的友元(23)关于动态存储分配，下列说法正确的是A)new和delete是C++语言中专门用于动态内存分配和释放的函数B)动态分配的内存空间也可以被初始化C)当系统内存不够时，会自动回收不再使用的内存单元，因此程序中不必用delete释放内存空间D)当动态分配内存失败时，系统会立刻崩溃，因此一定要慎用new(24)有以下程序#include<iostream>using namespace std;class MyClass{public:MyClass(int n){number = n;}4 C.) cout << "OK"; else cout << "FAIL";后，如果文件打开成功显示“OK”，否则就显示“F厶n。
数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。
A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中( )是非线性结构。
A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。
脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。
A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。
A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。
A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
2014年下半年网络管理员上午试卷（考试时间 9 : 00～11 : 30 共 150 分钟）1. 在答题卡的指定位置上正确写入你的姓名和准考证号，并用正规 2B 铅笔在你写入的准考证号下填涂准考证号。
2. 本试卷的试题中共有 75 个空格，需要全部解答，每个空格 1 分，满分75 分。
3. 每个空格对应一个序号，有 A、B、C、D 四个选项，请选择一个最恰当的选项作为解答，在答题卡相应序号下填涂该选项。
4. 解答前务必阅读例题和答题卡上的例题填涂样式及填涂注意事项。
解答时用正规 2B 铅笔正确填涂选项，如需修改，请用橡皮擦干净，否则会导致不能正确评分。
例题● 2014年下半年全国计算机技术与软件专业技术资格（水平）考试日期是（88）月（89）日。
（88）A. 9 B. 10 C. 11 D. 12（89）A. 4 B. 5 C. 6 D. 7 因为考试日期是“11 月 4 日”，故（88）选 C，（89）选 A，应在答题卡序号 88 下对 C 填涂，在序号 89 下对 A 填涂（参看答题卡）。
●微型计算机系统中，显示器属于（1），硬盘属于（2）。
(1)A.表现媒体 B.传输媒体 C.表示媒体 D.存储媒体(2)A.表现媒体 B.传输媒体 C.表示媒体 D.存储媒体●以下设备中，不能使用（3）将印刷图片资料录入计算机。
(3)A.扫描仪 B.投影仪 C.数字摄像机 D.数码相机●机器字长为8位，定点整数X的补码用十六进制表示为B6H，则其反码用十六进制表示为（4）。
(4)A.CAH B.B6H C.4AH D.B5H●在定点二进制运算中，减法运算一般通过（5）来实现。
(5)A.补码运算的二进制减法器 B.原码运算的二进制减法器C.原码运算的二进制加法器D.补码运算的二进制加法器●下列编码中包含奇偶校验位、无错误，且采用偶校验的编码是（6）。
(6)A.10101101 B.10111001 C.11100001D.10001001●直接转移指令执行时，是将指令中的地址送入（7）。
1一、单项选择题1．算法指的是（ D ） D ．解决问题的有限运算序列2．线性表采用链式存储时，结点的存储地址（ B ）B ．连续与否均可3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ C ）A ．O （1)B ．O(n ）C ．O （m ）D ．O （m+n ）4．由两个栈共享一个向量空间的好处是：（ B ） B ．节省存储空间,降低上溢发生的机率5．设数组data ［m ］作为循环队列SQ 的存储空间,front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为( D) D ．front=（front+1)%m6．如下陈述中正确的是（ A ） A ．串是一种特殊的线性表7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ C ) C ．O （n 2）8．一个非空广义表的表头（ D ） D ．可以是子表或原子9对应的稀疏矩阵是（ A ） ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡--00000405000000076080.A10．在一棵度为3的树中，度为3的结点个数为2，度为2 的结点个数为1,则度为0的结点个数为( C ) C ．611．在含n 个顶点和e 条边的无向图的邻接矩阵中,零元素的个数为（ D ) D ．n 2－2e12．假设一个有n 个顶点和e 条弧的有向图用邻接表表示,则删除与某个顶点v i 相关的所有弧的时间复杂度是( C ) C ．O （n+e)13．用某种排序方法对关键字序列（25，84，21，47，15,27，68，35，20）进行排序时,序列的变化情况如下：20，15，21，25，47，27,68，35，8415,20，21,25,35，27，47，68，8415，20，21，25，27,35,47，68，84则所采用的排序方法是（ D ) D ．快速排序14．适于对动态查找表进行高效率查找的组织结构是（ C ） C ．三叉排序树15．不定长文件是指（B ） B ．记录的长度不固定二、填空题16．数据的逻辑结构是从逻辑关系上描述数据,它与数据的 存储（存储结构） 无关，是独立于计算机的.17．在一个带头结点的单循环链表中,p 指向尾结点的直接前驱，则指向头结点的指针head可用p 表示为head= p-〉next —>next 。
全国2011年1月自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。
错选、多选或未选均无分。
1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( )A.O(1)B.O(n)C.O(log2n)D.O(n)2.树形结构中，度为0的结点称为( )A.树根B.叶子C.路径D.二叉树3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>，<V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>}，则图G的拓扑序列是( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义，表述正确的是( )A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指( )A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6.组成数据的基本单位是( )A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n；x=0；do{x=x+5*i；i--；}while （i>0）；的时间复杂度为( )A.O（1）B.O（n）C.O（n2）D.O(n3)8.与串的逻辑结构不同的．．．数据结构是( )A.线性表B.栈C.队列D.树9.二叉树的第i（i≥1）层上所拥有的结点个数最多为( )A.2iB.2iC.2i-1D.2i-110.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( ) A.p->next=p->next->next B.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.直接插入排序D.快速排序12.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为( )A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为( )A.LL型B.LR型C.RL型D.RR型14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为( )A.1B.3C.4D.515.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是( )A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。
