北交数据结构 -徐薇 -第九章作业

北交《计算机联锁技术》复习题解析A一、填空题1.目前比较常用的进路表型静态数据结构有（）、联锁表型静态数据结构、相关进路型联锁。

考核知识点解析：进路表型静态数据结构的分类正确选项：因果关联型联锁2.参与联锁运算的动态数据主要包括（）、状态输入变量、表示输出变量、控制输出变量。

考核知识点解析：联锁运算的动态数据分类正确选项：操作输入变量3.在进路正常通过解锁子模块中，自动解锁包括（）和调车进路的中途返回解锁。

考核知识点解析：自动解锁正确选项：进路正常通过解锁4.故障产生的原因有系统内部元器件的缺陷、系统外部环境条件变化、（）。

考核知识点解析：故障产生的原因正确选项：有目的的对系统破坏5.解决线路干扰常用的技术措施包括合理布置元器件和布线、妥善处理好电源馈线、采用滤波器、（）。

考核知识点解析：线路干扰正确选项：采用屏蔽措施6.动态冗余结构的方式有（）、冷备、温备三种方式。

考核知识点解析：动态冗余结构的方式正确选项：热备7.按持续期分类，计算机系统故障可分为（）、瞬间故障、间歇故障三种。

考核知识点解析：计算机系统故障的分类正确选项：永久故障8.硬件同步方式主要包括共同时钟方式、时钟反馈调节方式、（）。

考核知识点解析：正确选项：事件调节同步方式9.系统中常用的故障检测方法有自检互检法、仲裁法、比较法、（）。

考核知识点解析：故障检测方法正确选项：自检法10.在数字信号传输中，抗干扰措施包括开关触点抖动的控制、负逻辑传输方式、提高输入端的门限电压、（）。

考核知识点解析：抗干扰的措施正确选项：线间串扰的抑制二、简答题11.TYJL-II型计算机联锁系统联锁死机的表现特征及解决方法？考核知识点解析：TYJL-II型计算机联锁系统联锁死机的表现特征及解决方法正确选项：死机的表现：联锁机计算机层运行灯停止闪烁；联锁机计算机层中断2灯停止闪烁；采集板板选指示灯停止闪烁；第一块驱动板一、四灯位灭灯。

处理方法：若联锁机主备机处于热备同步状态则主备机将自动倒机，备机自动提升为工作及备机脱机；若联锁机主备机处于非热备同步状态则人工扳动切换旋钮将备机提升为工作机，将切换旋钮恢复至自动位置，然后在控制台实施上电解锁。

7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000 一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

试指出下列各表中使用的是何种存储方式：表1是(（2）)存储方式；表2是(（3）)存储方式；表3是(（4）)存储方式；表4是(（5）)存储方式。

表左的s指向起始表元。

供选择的答案：A.连续B.单向链接C.双向链接D.不连接E.循环链接F.树状G.网状H.随机I.顺序J.顺序循环【上海海运学院 1995 二、1（5分）】12.(1) 静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第i个元素的时间与i无关。

(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是（）【南京理工大学 2000 一、3（1.5分）】A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）13. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24．在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

第三章习题1.按图3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：⑴如进站的车厢序列为123，则可能得到的出站车厢序列是什么？⑵如进站的车厢序列为123456，能否得到435612和135426的出站序列，并说明原因。

（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。

2.设队列中有A、B、C、D、E这5个元素，其中队首元素为A。

如果对这个队列重复执行下列4步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。

直到队列成为空队列为止，得到输出序列：（1）A、C、E、C、C （2） A、C、E（3） A、C、E、C、C、C （4） A、C、E、C3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B＊Ｃ／Ｄ＋Ｅ↑Ｆ5.试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1& 序列2’模式的字符序列。

其中序列1和序列2中都不含字符’&’，且序列2是序列1的逆序列。

例如，‘a+b&b+a’是属该模式的字符序列，而‘１+３&３－１’则不是。

6.假设表达式由单字母变量和双目四则运算算符构成。

试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式。

7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。

9.简述以下算法的功能（其中栈和队列的元素类型均为int）：（1）void proc_1(Stack S){ int i, n, A[255];n=0;while(!EmptyStack(S)){n++; Pop(&S, &A[n]);}for(i=1; i<=n; i++)Push(&S, A[i]);}（2）void proc_2(Stack S, int e){ Stack T; int d;InitStack(&T);while(!EmptyStack(S)){ Pop(&S, &d);if (d!=e) Push( &T, d);}while(!EmptyStack(T)){ Pop(&T, &d);Push( &S, d);}}（3）void proc_3(Queue *Q){ Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)){DeleteQueue(Q, &d);Push( &S, d);}while(!EmptyStack(S)){ Pop(&S, &d);EnterQueue(Q，d)}}实习题1．回文判断。

if(pa) /*若表A未完，将表A中后续元素链到新表C表*/ { smaller=pa; pa=pa－>next; smaller－>next = c－>next; c－>next = smaller; } /*否则将表B中后续元素链到新表C表尾*/
else {
smaller=pb; pb=pb－>next; smaller－>next = c－>next; c－>next = smaller; }
return(C); }
西北大学可视化技术研究所
10.已知有单链表表示的线性表中含有三类字 符的数据元素（如字母字符，数字字符和其它 字符），试编写算法来构造三个以循环链表表 示的线性表，使每个表中只含同一类的字符， 且利用原表中的结点空间作为这三个表的结点 空间，头结点可另辟空间。
西北大学可视化技术研究所
西北大学可视化技术研究所
答案：435612不可以 原因 （1）S：1234 X：43 （2）S：5 X: 5 （3）S：6 X: 6 （4）X：21 135426 可以 原因（1）S：1 X：1 （2）S：23 X: 3 （3）S：45 X: 54 （4）X：2 （5）S：6 X: 6
西北大学可视化技术研究所
G. S->next= NULL; 。
西北大学可视化技术研究所
供选择的语句有：
A. P->next=S; B. P->next= P->next->next; C. P->next= S->next;
E. S->next= P->next; F. S->next= L;
G. S->next= NULL;

11．在下面的程序段中，对x 的赋值语句的频度为（c ）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（d ）A． O（n） B. O(nlogn) C. O(n3) D. O(n2)3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( f)5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

( t)8．数据的物理结构是指数据在计算机内的实际存储形式。

(t )13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (f ) 3．数据的逻辑结构是指:数据的组织形式，即数据元素之间逻辑关系的总体。

而逻辑关系是指数据元素之间的关联方式或称“邻接关系”4．一个数据结构在计算机中称为存储结构:表示（又称映像）9．已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGINx:=x+1；{语句2}FOR j:=n DOWNTO i DO {语句3}y:=y+1; {语句4}END；语句 1 执行的频度为（1）；语句2 执行的频度为（2）；语句3 执行的频度为（3）；语句4 执行的频度为（4）。

9．（1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。

10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n 的函数）FOR i：＝１ TO n DOFOR j：＝１ TO i DOFOR k：＝1 TO j DOｘ：＝ｘ＋delta；10．1+（1+2++（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 O(n3)3. 数据类型和抽象数据类型是如何定义的。

12.将软件组装成系统的一种测试技术叫(). A.集成测试 B.单元测试 C.集合测试 D.系统测试
13.下列关于进程的描述错误的是()。 A.进程是动态的 B.进程有生命期 C.多个进程可以并行执行，不需同步机构 D.程序的执行过程是进程
14.线性链表的地址()。 A.必须连续 B.部分地址必须连续 C.一定不连续 D.连续与否均可以
10.存储器的读写速度排列顺序正确的是()。 A.RAMCache硬盘软盘 B.CacheRAM硬盘软盘 C.Cache硬盘RAM软盘 D.RAM硬盘软盘Cache
11.面向数据的设计方法就是根据问题的数据结构定义一组映射,把问题的数据结构转换为问题解的 ()结构 A.程序 B.数据 C.逻辑 D.物理
7.从事物的组成部件及每个部件的属性,功能来认识事物.这种方法被称为()的方法. A.面向对象 B.面向数据 C.面向过程 D.面向属性
8.Jackson方法在需求分析阶段的主要步骤不包括(). A.了解实体行为 B.标识实体与行为
C.生成实体结构图 D.创建软件系统模型
9.在下列功能中，()最好地描述了OSI模型的网络层。 A.保证数据正确的顺序、无错和完整 B.提供用户与网络的接口 C.处理信号通过介质的传输 D.控制报文通过网络的路由选择
4.分配到必要资源并获得了处理机时的进程状态称为()。 A.就绪状态 B.执行状态 C.等待状态 D.阻塞状态
5.人机界面的风格大致经过了()代的演变. A.三 B.四 C.五 D.六
6.为改正软件系统中潜藏的错误而进行的维护活动称为() A.纠错性维护 B.适应性维护 C.改善性维护 D.预防性维护
18.软件的发展经历了()个发展阶段 A.1 B.2 C.3 D.4
19.有一数列：87 55 66 13 19 39 48 经过一趟排序后得到： 55 87 13 66 19 39 48 请问使用的 是何种排序方法？() A.简单插入排序 B.冒泡排序 C.2路归并排序 D.快速排序

北交《管理信息系统》在线作业一、单选题（共 15 道试题，共 45 分。

）1.日常事务处理信息适用于（）. 中层管理. 高层管理. 基层管理. 目标管理正确答案：2.信息报告系统的特点是（）. 能提供决策时所需要的一切数据资料. 按事先规定的要求提供管理报告. 按随机输入的要求进行策略分析. 在决策过程中提供最佳选择方案正确答案：3.在面向对象的开发方法中，下面那一项不是对象最突出的特征（）。

. 封装性. 继承性. 多态性. 可靠性正确答案：4.决策支持系统是管理信息系统的一个重要分支，它是（）. 决程序性决策问题. 解强调支持而不是代替决策. 为业务层服务. 既能支持又可代替人的决策正确答案：5.计算机中对大量数据存贮管理的方式是（）。

. 人工管理与联机管理方式. 顺序存取方式与随机存取方式. 文件方式与数据库方式. 数据管理与操作管理方式正确答案：6.根据不同级别管理者对管理信息的需要，通常把管理信息分为以下三个等级. 公司级、工厂级、车间级. 工厂级、车间级、工段级. 厂级、处级、科级. 战略级、策略级、作业级正确答案：7.系统常用的转换方式中没有（）. 并行转换. 间接转换. 分阶段转换正确答案：8.在任一组织内同时存在着三个不同的计划控制层是（）. 战略计划层，管理控制层，操作层. 战略计划层，战术计划层，管理层. 战略计划层，业务计划层，操作层. 战术计划层，管理控制层，操作层正确答案：9.现代信息信息技术的核心是（）. 缩微技术. 电子计算机和现代通讯技术. 现代办公设备. 遥感遥测技术正确答案：10.管理控制信息是属于管理信息的（）。

. 战略级. 策略级. 作业级. 操作级正确答案：11.不属于直接存取文件组织的实现方法是（）。

. 直接地址法. 相对键法. 杂凑法. 分块法正确答案：12.对当前系统进行初步调查工作应重点在哪个阶段进行（） . 总体规划阶段. 系统分析阶段. 系统设计阶段. 系统实施阶段正确答案：13.信息系统开发的结构化方法的一个主要原则是. 自顶向下原则. 自底向上原则. 分布实施原则. 重点突破原则正确答案：14.< 下述哪一项不是信息系统逻辑模型的组成部分（）. 业务流程图. 数据流程图. 系统流程图正确答案：15.不属于联机实时处理方式的情况是（） . 需要反应迅速的数据处理. 负荷易产生波动的数据处理. 数据收集费用较高的数据处理. 固定周期的数据处理正确答案：北交《管理信息系统》在线作业二、多选题（共 5 道试题，共 15 分。

北交《数据结构（专）》在线作业一
一,单选题
1. 一个队的入队序列是1，2，3，4 ，则队列的输出序列是（）。

A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，1，4
?
正确答案：B
2. 设有一个二元数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676 (10)，每个元素占一个空间，则A[4][5]在（）位置，(10)表明用10进数表示。

A. 692(10)
B. 626(10)
C. 709(10)
D. 724(10)
?
正确答案：C
3. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A. 插入
B. 交换
C. 选择
D. 归并
?
正确答案：A
4. 算法分析的目的是（)。

A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
?
正确答案：C
5. 队列操作的原则是（）。

A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
?。

1.线索化二叉树中某结点D，没有左孩子的主要条件是（）。

A.D-Lchild=NullB.D-ltag=1C.D-Rchild=NullD.D-ltag=0【参考答案】: B2.具有2000个节点的二叉树，其高度至少为（）。

A.9B.10C.11D.12【参考答案】: C3.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。

A.8B.63.5C.64D.7【参考答案】: B4.树最适合用来表示（）。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据【参考答案】: C5.若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。

A.3，2，1B.2，1，3C.3，1，2D.1，3，2【参考答案】: C6.计算机的算法是（）。

A.计算方法B.排序方法C.对特定问题求解步骤的一种描述D.调度算法【参考答案】: C7.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。

A.起泡排序B.快速排序C.简单选择排序D.堆排序【参考答案】: D8.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。

A.O（nlog2e）B.O（ne）C.O(n*e)D.O(n*n)【参考答案】: B9.邻接表是图的一种（）。

A.顺序存储结构B.链式存储结构C.索引存储结构D.列存储结构【参考答案】: B10.若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是（）。

A.根结点无右子树的二叉树B.根结点无左子树的二叉树C.根结点可能有左二叉树和右二叉树 D.各结点只有一个儿子的二叉树【参考答案】: C11.完成堆排序的全过程需要 ( )个纪录大小的辅助空间。

A.1B.nC.nlog2nD.|nlog2n|【参考答案】: A12.采用顺序查找方法查找长度为n的线性表时，每个元素的平均长度为( ）。

√
13. 关于杂凑查找说法不正确的有几个 ) 【南京 关于杂凑查找说法不正确的有几个( 理工大学 2000 一、16 （1.5分）】 分 （1）采用链地址法解决冲突时，查找一个元素的 ）采用链地址法解决冲突时， 时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是 ）采用链地址法解决冲突时， 在链首， 在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 ） （4）再哈希法不易产生聚集 ） A. 1 B. 2 C. 3 D. 4
√
14. 设哈希表长为 ，哈希函数是 设哈希表长为14， H(key)=key%11,表中已有数据的关键字为 ， 表中已有数据的关键字为15， 表中已有数据的关键字为 38，61，84共四个，现要将关键字为 的结点加 共四个， ， ， 共四个 现要将关键字为49的结点加 到表中，用二次探测再散列法解决冲突， 到表中，用二次探测再散列法解决冲突，则放入 的位置是( 的位置是 ) 【南京理工大学 2001 一、15 （1.5分）】 分 A．8 B．3 C．5 D．9 ． ． ． ．
第九章 习题
一、 选择题 1.若查找每个记录的概率均等，则在具有 个记录 若查找每个记录的概率均等， 若查找每个记录的概率均等 则在具有n个记录 的连续顺序文件中采用顺序查找法查找一个记录， 的连续顺序文件中采用顺序查找法查找一个记录， 其平均查找长度ASL为( )。【北京航空航天大学 其平均查找长度 为 。 2000 一、8 （2分）】 分 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n ．
5．分别以下列序列构造二叉排序树，与用其它 ．分别以下列序列构造二叉排序树， 三个序列所构造的结果不同的是( 三个序列所构造的结果不同的是 ) 【合肥工业 大学2000一、4（2分）】 大学 一 （ 分 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) ， ， ， ， ， ，

北交《语言程序设计》在线作业一一、单选题（共 15 道试题，共 30 分。

）1. 不合法的八进制数是(). 0. 028. 077. 01正确答案：2. 若有以下定义和语句： int [10]={1,2,3,4,5,6,7,8,9,10},*p=; 则不能表示数组元素的表达式是____。

. *p. [10]. *. [p-]正确答案：3. 下面说法错误的是______。

. 整型变量可以存放字符型数据. 字符型变量可以存放任意整型常量的值. 变量必须限定以后使用. 字符串的长度不等于它占的字节数正确答案：4. 已知int m,n,i=2；执行语句m=-i++；n=++i；后，m和n的值分别是_____。

. -3 4. -2 4. -3 3. -2 3正确答案：5. 若有输入语句snf( "%%%"， &x,&y,&z);则不能使x值为5， y值为6， z值为7的输入是______。

. 5,6 ,7&lt;回车&gt;. 5 6 7&lt;回车&gt;. 5 6 &lt;回车&gt; 7&lt;回车&gt;. 5&lt;回车&gt;，6&lt;回车&gt;，7&lt;回车&gt;正确答案：6. 语言源程序文件经过编译程序编译连接之后生成一个后缀为()的文件。

. ”.”. “.oj”. “.x”. “.s”正确答案：7. 语言是_______语言。

. 高级. 中级. 机器. 汇编正确答案：8. 设n=3;则执行 ++n语句后，n的值为_____。

（）. 5. 4. 3. 2正确答案：9. 语言程序从min()函数开始执行，所以这个函数要写在____。

. 程序文件的开始. 程序文件的最后. 它所调用的函数的前面. 程序文件的任何位置正确答案：10. 执行以下程序段后， x， y和z的值分别是______。

第七章 图一、选择题1．图中有关路径的定义是（ ）。

【北方交通大学 2001 一、24 （2分）】A ．由顶点和相邻顶点序偶构成的边所形成的序列B ．由不同顶点所形成的序列C ．由不同边所形成的序列D ．上述定义都不是2．设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n 2【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。

【浙江大学 1999 四、4 (4分)】A ．n-1B ．nC ．n+1D ．nlogn ；4．要连通具有n 个顶点的有向图，至少需要（ ）条边。

【北京航空航天大学 2000 一、6(2分）】A ．n-lB ．nC ．n+lD ．2n5．n 个结点的完全有向图含有边的数目（ ）。

【中山大学 1998 二、9 （2分）】A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ）6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0B ．1C ．n-1D ．n【北京邮电大学 2000 二、5 （20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

【哈尔滨工业大学 2001 二、3 （2分）】A ．1/2B ．2C ．1D ．48．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。

【中山大学1999一、14】A ．5B ．6C ．8D ．99．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A ．逆拓扑有序B ．拓扑有序C ．无序的 【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。

计算机专业基础综合数据结构（集合）历年真题试卷汇编5计算机专业基础综合数据结构（集合）历年真题试卷汇编5(总分：66.00，做题时间：90分钟)⼀、单项选择题(总题数：21，分数：46.00)1.含有n个⾮叶⼦结点的m阶B⼀树⾄少包含( )个关键字。

【北京交通⼤学20041A.(m-1) * nB.nC.n * (m／2-1)D.(n⼀1) * (m／2-1)+1 √2.理论上，散列表的平均⽐较次数为( )次。

【北京邮电⼤学2005⼀、9(2分)】A.1 √B.2C.4D.n3.散列函数有⼀个共同的性质，即函数值应当以( )取其值域的每个值。

【西安电⼦科技⼤学2001计算机应⽤⼀、7(2分)】【北京邮电⼤学。

1999⼀、4(2分)】A.最⼤概率B.最⼩概率C.平均概率D.同等概率√4.将10个元素散列到100000个单元的哈希表中，则( )产⽣冲突。

【北京邮电⼤学2001⼀、4(2分)】A.⼀定会B.⼀定不会C.仍可能会√5.采⽤链地址法解决冲突的哈希表中，查找成功的平均查找长度( )。

【北京交通⼤学2005⼀、6(2分)2007】A.直接与关键字个数有关B.直接与装填因⼦有关C.直接与表的容量有关D.直接与哈希函数有关√链地址法解决冲突，是动态申请结点，容量只受内存所限。

6.下⾯关于哈希(Hash，杂凑)查找的说法正确的是( )。

【南京理⼯⼤学1998⼀、10(2分)】【烟台⼤学2007⼀、1 8(2分)】A.哈希函数构造的越复杂越好，因为这样随机性好，冲突⼩B.除留余数法是所有哈希函数中最好的C.不存在特别好与坏的哈希函数，要视情况⽽定√D.若需在哈希表中删去⼀个元素，不管⽤何种⽅法解决冲突都只要简单地将该元素删去即可7.在构造哈希表⽅⾯，下⾯的说法( )是正确的。

【华南理⼯⼤学2005⼀、1(2分)】A.再散列在处理冲突时不会产⽣“聚集”B.散列表的装载因⼦越⼤，说明空间利⽤率越好，因此应使装载因⼦尽量⼤C.散列函数选得好可减少冲突现象√D.对于任何具体关键字都不可能找到不产⽣冲突的散列函数8.在构造散列表⽅⾯，下⾯的说法( )是正确的。

已知待排序的n个元素可分为nk个组每个组包含k个元素且任一组内的各元素均分别大亍前一组内的所有元素和小亍后一组内的所有元素若采用基亍比较的排序其时间下界应为oklog2k中国科技大学1998类似本题的另外叙述有
第 10 章
排序
一、选择题 1．某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2 分） 】 A． 该排序算法不允许有相同的关键字记录 B． 该排序算法允许有相同的关键字 记录 C．平均时间为 0（n log n）的排序方法 D．以上都不对 2． 下面给出的四种排序法中( )排序法是不稳定性排序法。 【北京航空航天大学 1999 一、 10 （2 分） 】 A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3．下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2 分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4．稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2 分） 】 A．直接插入排序和快速排序 B．折半插入排序和起泡排序 C．简单选择排序和四路归并排序 D．树形选择排序和 shell 排序 5．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学 2001 一、8 （2 分） 】 A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序 6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒 泡排序） 。 【北京邮电大学 2001 一、5（2 分） 】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒， 则称该排序算法是不稳定的。 （ ）就是不稳定的排序方法。 【清华大学 1998 一、3 (2 分） 】 A．起泡排序 B．归并排序 C．Shell 排序 D．直接插入排序 E．简单选 择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数 【中科院计算所 2000 一、 5（2 分） 】 9．若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方 法是（ ） 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 【中国科技大学 1998 二、4（2 分） 】 【中科院计算所 1998 二、4（2 分） 】 10．下面的排序算法中，不稳定的是（ ） 【北京工业大学 1999 一、2 (2 分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆 排序。 11．下列内部排序算法中： 【北京工业大学 2000 一、1 (10 分 每问 2 分)】 A．快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ） （3）在初始序列已基本有序（除去 n 个元素中的某 k 个元素后即呈有序，k<<n）的情况下， 排序效率最高的算法是（ ） （4）排序的平均时间复杂度为 O(n•logn)的算法是（ ）为 O(n•n)的算法是（ ）

西北大学可视化技术研究所
q=p; p=p->next; b->next=q; q->next=B; b=b->next; } else {//分出其他字符结点 q=p; p=p->next; c->next=q; q->next=C; c=c->next; } } }//结束
西北大学可视化技术研究所
A．双向链表
B．双向循环链表
C．单向循环链表 D．顺序表
（4）下列选项中， D 项是链表不具有的特点。
A．插入和删除运算不需要移动元素
B．所需要的存储空间与线性表的长度成正比
C．不必事先估计存储空间大小
D．可以随机访问表中的任意元素
西北大学可视化技术研究所
(5)在链表中最常用的操作是删除表中最后一个结点和 在最后一个结点之后插入元素，则采用 C 最 节省时间。
西北大学可视化技术研究所
8.假设两个按元素值递增有序排列的线性 表A和B，均以单链表作为存储结构，请 编写算法，将A表和B表归并成一个按元 素值递减有序排列的线性表C，并要求利 用原表（即A表和B表的）结点空间存放 表C。
西北大学可视化技术研究所
算法描述：要求利用现有的表A和B中的结 点空间来建立新表C，可通过更改结点的next 域来重新建立新的元素之间的线性关系。为保 证新表递减有序可以利用头插法建立单链表的 方法，只是新建表中的结点不用malloc，而只 需要从A和B中选择合适的点插入到新表C中即 可。
西北大学可视化技术研究所
1.3填空题： （1）变量的作用域是指 变量的有效范围 （2）抽象数据类型具有 数据抽象 、 信息隐 蔽 的特点。 （3）一种抽象类型包括 数据对象 、 结构 关系 和 基本操作 。