南京理工大学877计算机专业基础C 03-16年真题

计算机专业基础综合数据结构（排序）历年真题试卷汇编3(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。

【北京航空航天大学1999一、10(2分)】A.插入B.冒泡C.二路归并D.堆√2.下列排序算法中，其中( )是稳定的。

【福州大学1998一、3(2分)】A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序√3.稳定的排序方法是( )。

【北方交通大学2000二、3(2分)】A.直接插入排序和快速排序B.折半插入排序和起泡排序√C.简单选择排序和四路归并排序D.树形选择排序和Shell排序4.下列排序方法中，哪一个是稳定的排序方法?( )。

【北方交通大学2001一、8(2分)】A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序5.下列排序算法中，( )是稳定排序。

【北京理工大学2007一、10(1分)】A.希尔排序B.快速排序C.堆排序D.直接插入排序√6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

( )就是不稳定的排序方法。

【清华大学1998一、3(2分)】A.起泡排序B.归并排序C.Shell排序√D.直接插入排序E.简单选择排序√7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。

【中科院计算所2000一、5(2分)】A.直接插入√B.直接选择C.堆D.快速E.基数8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】A.快速排序B.堆排序C.归并排序√D.直接插入排序9.下面的排序算法中，不稳定的是( )。

【北京工业大学1999一、2(2分)】A.起泡排序B.折半插入排序C.简单选择排序√D.希尔排序√E.基数排序下列内部排序算法中：【北京工业大学2000一、1(10分每问2分)】A．快速排序B．直接插入排序C．二路归并排序D．简单选择排序E．起泡排序（分数：8.00）(1).其比较次数与序列初态无关的算法是( )A.B.C. √D. √E.(2).不稳定的排序算法是( )A. √B.C.D. √E.(3).在初始序列已基本有序(除去n个元素中的某k个元素后即呈有序，k<A.B. √C.D.E.(4).排序的平均时间复杂度为O(n*10gn)的算法是( )，为O(n*n)的算法是( )A. √B. √C. √D. √E. √10.排序趟数与序列的原始状态有关的排序方法是( )排序法。

5、队列操作的特点是______________。 A)先进先出 B）后进先出 C）顺序存储 D）用于递归实现 6、含有 11 个结点的完全二叉树中，度为 1 的节点个数________。 A）0 B）1 C）2 D）5 7、对于三个结点 A、B、C，可构成_________种不同形态的二叉树。 A）4 B）5 C）30 D） 6 8. 当初始序列已按键值有序，则用简单选择排序算法对其进行排序，则需要进行的比较次数 为 。 A） N
2
B） N 1 C） N * log 2 )
N
D） N * ( N 1) / 2
9. 有二维数组 B[1...20,0...5]按行优先顺序存放，设 B[1,0]的存储地址为 600，每 个元素占 3 个单元，则 B[3,2]的地址为 。 A)630 B) 636 C) 642 D) 645 10．已知一棵完全二叉树的第 6 层（设根为第一层）有 9 个叶子结点，则该完全二叉 树的节点个数为 。 A)40 B) 51 C) 109 D) 120 11． 若数据元素序列 11,12,13,8,9,10,25,5,6 是采用下列排序方法之一得到的第二趟 排序后的结果，则该排序算法只能是 。 A)插入排序 B)冒泡排序 C)二路归并排序 D)选择排序 12．一棵度为 4 的树 T 中，若有 5 个度为 4 的结点，6 个度为 3 的结点，4 个度为 2 的 结点，2 个度为 1 的结点，则树 T 中叶子结点的个数为 。 A)17 B) 34 C)32 D) 48 13.已知一个长度为 20 的顺序表 L，其元素按键值有序排列。若用折半查找法查找 L 中不存在的元素，则关键字的比较次数最多的是 。 A) 4 B)5 C)6 D) 7 14．对同一个待排序列分别采用折半插入排序和直接插入排序，两者之间可能的不同之处

。
12.影响文件安全性的主要因素有： （41）
，（42）
，（43）
。
13.在为文件分配外空间时，所要考虑的问题主要有：（44）
，（45）
。
14.UNIX 系 统 中 ， 系 统 进 程 上 下 文 包 括 ：（46 ）
和 （ 47 ）
。
15.在UNIX系统中，管道可分为： （48）
和（49）
。
16.在UNIX系统中，为实现请求调页管理，在核心配置了以下四中数据结构：（50）
8. 设一棵后序线索树的高是50，结点x是树中的一个结点，其双亲是结点y,y 的右子树 高度是31，x是y的左孩子。则确定x的后继最多需经过 （17） 中 间结点（不含后继 及x本身） 9. 设F是由T1、T2、T3三棵树组成的森林，与F对应的二叉树为B，已知T1、T2、
T3的结点数分别为 n1、n2、n3，则二叉树B的左子树中有 （18） 个结点，右 子树中 有 （19） 个结点。 10. 设有三对角矩阵如下图
置是
（A）A[2i](2i≦n)
（B）A[2i+1](2i+1≦n) (C)A[i/2]
(D)条件不充分，无法确定
5.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度 是
（A）4 （B）5 （C）6 （D）7
6.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S，一个 元素出栈后
，（ 51 ）
，（ 52 ）
，（ 53 ）
。
17.在UNIX系统中，系统向用户提供的用于对进程进行控制的系统调用：（1）fork 用于
（54）
；（2）exec用于（55）
；（3）exit 用于（56）

计算机专业基础综合操作系统（输入／输出管理）历年真题试卷汇编1计算机专业基础综合操作系统（输入／输出管理）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.单项选择题下列各题的备选答案中，只有一个是符合题意的。

（分数：2.00）________________________________________________________________ __________________________ 解析：2.虚拟设备是指____。

【南京理工大学2002年】（分数：2.00）A.允许用户使用比系统中具有的物理设备更多的设备B.允许用户以标准化方式来使用物理设备C.把一个物理设备变换成多个对应的逻辑设备√D.允许用户程序不必全部装入主存便可使用系统中的设备解析：解析：考查虚拟设备的定义。

3.在操作系统中，用户在使用I／O设备时，通常采用____。

【兰州大学2005年】（分数：2.00）A.物理设备名B.逻辑设备名√C.虚拟设备名D.设备序号解析：解析：考查I／O设备管理的基本概念。

此题在2010年统考真题中有涉及。

没有虚拟设备名一说。

4.____是操作系统中采用的以空间换取时间的技术。

【北京理工大学2004年】（分数：2.00）A.SPOOLing技术√B.虚拟存储技术C.覆盖与交换技术D.通道技术解析：解析：综合考查操作系统中的几种技术。

SPOOLing技术通过建立缓冲区(输入井、输出井)，使得物理上独占的设备实现逻辑共享，从而提高设备的利用率，使得系统效率提高。

5.关于SPOOLing技术，下列说法错误的是____。

（分数：2.00）A.SPOOLing技术是缓冲技术的应用B.SPOOLing技术是一种虚拟设备技术C.SPOOLing技术是一种设备驱动技术√D.SPOOLing技术提高了独占设备的利用率解析：解析：考查SPOOLing技术的基本概念。

计算机专业基础综合数据结构（排序）历年真题试卷汇编5(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。

【2009年全国试题9(2分)】A.3，5，12，8，28，20，15，22，19 √B.3，5，12，19，20，1 5，22，8，28C.3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，1 5，22，19首先按所给关键字序列画出完全二叉树，关键字3插入结点22的后边。

沿结点3到根的路径调整堆，直到满足堆的定义为止。

2.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。

【2009年全国试题10(2分)】A.起泡排序B.插入排序√C.选择排序D.二路归并排序起泡排序的特点是待排序元素相邻两两比较，逆序交换，每趟有一个最大元素到达底部(或一个最小元素到达顶部)；插入排序的特点是先假定第一个元素有序，从第二个元素起，每趟将未排序元素的第一个元素插入的前面有序子文件中；选择排序的特点是第一趟在待排序元素中选最小(或最大)元素和第一个元素交换，第二趟在未排序元素中选次小(或次大)和第二个元素交换；二路归并排序是两两归并，再四四归并，等等。

3.采用递归方式对顺序表进行快速排序。

下列关于递归次数的叙述中，正确的是( )。

【2010年全国试题10(2分)】A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关√快速排序和数据的初始排列次序相关。

每次划分后，先处理较短分区可以减少递归深度，递归次数和先处理哪个分区无关。

4.对一组数据(2，12，1 6，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是( )。

计算机专业基础综合数据结构（查找）历年真题试卷汇编1(总分108,考试时间90分钟)1. 单项选择题1. 顺序查找法适合于存储结构为____的线性表。

【北京航空航天大学2002年】A. 顺序存储结构或链式存储结构B. 散列存储结构C. 索引存储结构D. 压缩存储结构2. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为____。

【北京航空航天大学2004年】A. (n—1)／2B. n／2C. (n+1)／2D. n3. 当采用分块查找时，数据的组织方式为____。

【太原科技大学2007年】A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同4. 对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为____。

【华中科技大学2007年】A. 50B. 125C. 500D. [log22500]5. 下面关于二分查找的叙述正确的是____。

【南京理工大学1996年】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型、实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储6. 当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是____。

【北京航空航天大学2002年】A. (n+1)／2B. n／2C. log2(n+1)一1D. log2(n+1)7. 在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录．需要进行____次关键字值的比较。

【北京航空航天大学2004年】A. 0B. 4C. 5D. 158. 对一个长度为50的有序表进行折半查找，最多比较____次就能查找出结果。

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编7(总分：74.00，做题时间：90分钟)一、单项选择题(总题数：19，分数：38.00)1.若循环队列使用C数组A[m]存放其数据元素，已知头指针front指向队首元素，尾指针rear指向队尾元素后的空单元，则当前队列中的元素个数为( )。

【华中科技大学2007一、3(2分)】A.(rear—front+m)％m √B.rear-front+1C.rear-frontD.rear-front-12.设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为( )。

【电子科技大学2008一、4(2分)】A.front=rear √B.front=-MaxSizeC.front+1=rearD.rear=03.循环队列存储在数组A[0．m]中，则入队时的操作为( )。

【中山大学1999一、6(1分)】A.rear=rear+1B.rear=(rear-H)mod(m一1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1) √4.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?( )【浙江大学1999四、1(4分)】A.1和5B.2和4 √C.4和2D.5和15.已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有( )。

【西安交通大学1996三、3(3分)】A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对√双端队列的输出序列求解见四、36。

6.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。

【西安电子科技大学1996一、5(2分)】【烟台大学2007一、5(2分)】A.1234B.4132C.4231 √D.42137.最大容量为n的循环队列，队尾指针是rear，队头是frunt，则队空的条件是( )。

真题及部分参考答案
2009年南京理工大学计算机科学 与工程学院计算机专业基础考研
真题及部分参考答案
2010年南京理工大学计算机科学 与工程学院824计算机专业基础A
考研真题及部分参考答案
2011年南京理工大学计算机科学 与工程学院824计算机专业基础A
2003年南京理工大学计算机科学 与工程学院计算机专业基础考研
真题及部分参考答案
2004年南京理工大学计算机科学 与工程学院计算机专业基础考研
真题及部分参考答案
Байду номын сангаас
2005年南京理工大学计算机科学 与工程学院计算机专业基础考研
考研真题
目 录
2003年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案
2004年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案
2005年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案
2006年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案
2011年南京理工大学计算机科学与工程学院824计算机专业基础A考研 真题及部分参考答案
2012年南京理工大学计算机科学与工程学院824计算机专业基础A考研
真题及部分参考答案
2013年南京理工大学计算机科学与工程学院824计算机专业基础A考研 真题
2015年南京理工大学计算机科学与工程学院824计算机专业基础A考研 真题
2007年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案
2008年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案
2009年南京理工大学计算机科学与工程学院计算机专业基础考研真题及 部分参考答案

计算机专业基础综合数据结构（集合）历年真题试卷汇编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.在构造散列表⽅⾯，下⾯的说法( )是正确的。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编5(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.线性表是一个( )。

【电子科技大学2010一、1(2分)】【江苏大学2005一、1(2分)】（分数：2.00）A.有限序列，可以为空√B.有限序列，不能为空C.无限序列，可以为空D.无限序列，不能为空解析：2.线性表的顺序存储结构是一种( )。

【北京理工大学2006五、3(1分)】（分数：2.00）A.随机存取的存储结构√B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构解析：3.(多选)在下列叙述中， ( )是错误的。

【华中科技大学2006一、1(2分)】（分数：2.00）A.线性表的逻辑顺序与物理顺序总是一致的√B.二叉树的顺序存储结构比链式存储结构节省存储空间√C.二叉树的度小于等于2D.每种数据结构都具有两种基本运算(操作)：插入、删除元素(结点) √解析：4.能在O(1)时间内访问线性表的第i个元素的结构是( )。

【电子科技大学2011一、2(2分)】（分数：2.00）A.顺序表√B.单链表C.单向循环链表D.双向链表解析：5.下面关于线性表的叙述中，错误的是哪一个?( )【北方交通大学2001一、14(2分)】（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作√C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作解析：6.线性表是具有n个( )的有限序列(n>0)。

【清华大学1998一、4(2分)】（分数：2.00）A.表元素B.字符C.数据元素√D.数据项E.信息项解析：7.单链表中，增加一个头结点的目的是( )。

【厦门大学2003一、1(2分)】（分数：2.00）A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现√D.说明单链表是线性表的链式存储解析：8.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。

计算机专业基础综合数据结构（排序）历年真题试卷汇编3(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：36.00)1.下面给出的四种排序法中，( )排序法是不稳定性排序法。

【北京航空航天大学1999一、10(2分)】（分数：2.00）A.插入B.冒泡C.二路归并D.堆√解析：2.下列排序算法中，其中( )是稳定的。

【福州大学1998一、3(2分)】（分数：2.00）A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序√解析：3.稳定的排序方法是( )。

【北方交通大学2000二、3(2分)】（分数：2.00）A.直接插入排序和快速排序B.折半插入排序和起泡排序√C.简单选择排序和四路归并排序D.树形选择排序和Shell排序解析：4.下列排序方法中，哪一个是稳定的排序方法?( )。

【北方交通大学2001一、8(2分)】（分数：2.00）A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序解析：5.下列排序算法中，( )是稳定排序。

【北京理工大学2007一、10(1分)】（分数：2.00）A.希尔排序B.快速排序C.堆排序D.直接插入排序√解析：6.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。

( )就是不稳定的排序方法。

【清华大学1998一、3(2分)】（分数：2.00）A.起泡排序B.归并排序C.Shell排序√D.直接插入排序E.简单选择排序√解析：7.若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选( )排序为宜。

【中科院计算所2000一、5(2分)】（分数：2.00）A.直接插入√B.直接选择C.堆D.快速E.基数解析：8.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是( )。

【中国科技大学1998二、4(2分)】【中科院计算所1998二、4(2分)】（分数：2.00）A.快速排序B.堆排序C.归并排序√D.直接插入排序解析：9.下面的排序算法中，不稳定的是( )。

计算机专业基础综合数据结构（排序）历年真题试卷汇编6(总分108,考试时间90分钟)1. 单项选择题1. 某内部排序方法的稳定性是指____。

【南京理工大学1997年】A. 该排序算法不允许有相同的关键字记录B. 该排序算法允许有相同的关键字记录C. 平均时间为O(nlogn)的排序方法D. 以上都不对2. 若要求尽可能快地对序列进行稳定的排序，则应选____。

【北京邮电大学2001年】A. 快速排序B. 归并排序C. 冒泡排序D. 根排序3. 下列排序方法中，____是稳定的排序方法。

【北方交通大学2001】A. 直接选择排序B. 二分法插入排序C. 希尔排序D. 快速排序4. 对有n个记录的表做直接插入排序，在最好情况下，需比较____次关键字。

【华中科技大学2006年】A. n-1B. n+1C. n／2D. n(n-1)／25. 对n个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多____。

【北京交通大学2007年】A. 从大到小排列好的B. 从小到大排列好的C. 元素无序D. 元素基本有序6. 采用简单选择排序，比较次数与移动次数分别为____。

【南京理工大学2000年】A. O(n)，O(10gn)B. O(logn)，O(n*n)C. O(n*n)，O(n)D. O(nlogn)，O(n)7. 希尔排序属于____。

【太原科技大学2006年】A. 插入排序B. 交换排序C. 选择排序D. 归并排序8. 对序列{15，9，7，8，20，一1，4}用希尔排序方法排序，经一趟后序列变为{15，一1，4，8，20，9，7}则该次采用的增量是____。

【南京理工大学1999年】A. 1B. 4C. 3D. 29. 有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，下列算法不会出现此种情况的是____。

【北京交通大学2005年】A. 希尔排序B. 堆排序C. 冒泡排序D. 快速排序10. 从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于等于所选元素，而所选元素处在排序的最终位置。

2016年全国硕士研究生入学统一考试计算机学科专业基础综合真题(总分150, 做题时间180分钟)单项选择题每小题 2 分，共 80 分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1.已知表头元素为 c 的单链表在内存中的存储状态如下表所示现将 f 存放于 1014H 处并插入到单链表中，若 f 在逻辑上位于 a 和 e 之间，则 a,e,f 的“链接地址”依次是（）。

SSS_SINGLE_SELA1010H，1014H，1004HB1010H，1004H，1014HC1014H，1010H，1004HD1014H，1004H，1010H2.已知一个带有表头结点的双向循环链表L，结点结构为prev data next，其中， prev和next分别是指向其直接前驱和直接后继结点的指针。

现要删除指针p所指的结点，正确的语句序列是（）。

SSS_SINGLE_SELAp->next->prev=p->prev; p->prev->next=p->prev; free (p);Bp->next->prev=p->next; p->prey-> next=p->next; free (p);Cp->next->prev=p->next; p->prev->next=p->prev; free (p);Dp-> next-> prey=p->prey; p->prev->next=p->next; free (p);3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。

现有编号为1～9的9列列车，驶入的次序依次是8， 4， 2， 5， 3，9， 1， 6， 7。

若期望驶出的次序依次为1～9，则n至少是（）。

D[X]移=1101101
3.浮点加减运算中对阶的方法是（ ） A 将加/减数的阶码调整到和被加/减数的阶码一致 B 将被加/减数的阶码调整到和加/减数的阶码一致 C 将两数中较小的阶码调到和较大的阶码一致 D 将两数中较大的阶码调到和较小的阶码一致
4.存储周期是指（ ） A 存储器的读出时间 B 存储器的写入时间 C 存储器连续启动两次读操作所需间隔的最短时间 D 存储器一次读命令发出到数据稳定读出到数据总线所需时间
D 链式查询方式
二、填空（每空一分） 1.CPU 厂商将 1 ， 2 和 Cache 集成，构成 CPU。
2.浮点运算过程中，结果向右规格化的规格是：尾数 3 ，阶码 4 。
3.在 Cache-主存系统中，若主存中任意一块只能映射到 Cache 一个特定块（行）上，这种地 址映射方式称为 5 ，若主存中任意一块能映射到 Cache 任意一个块（行）上，这种地址 映射方式称为 6 。
3.5 个元素，入栈次序 A,B,C,D,E，出栈为 C,D 开头的出栈序列不可能是 A.CDEAB B.CDEBA C.CDBEA D.CDBAE
4.一个 n 阶对称矩阵 A，采用压缩存储方式（即按行优先方式只存放下三角部分），将其存 放在一堆数组 B 中。则元素 A[i][j]（i<j）在 B 中的存储位置（即 B 的下标）是
A.j(j+1)/2+i-1 B.j(j-1)/2+i C.j(j-1)/2+i+1 D.j(j-1)/2+i-1
5.在一颗二叉树中有两个结点 m 和 n，在该二叉树的前序遍历序列中 n 在 m 之前，但是在 其后序遍历序列中 n 在 m 之后，则 n，m 关系是
A.n 是 m 子孙 B.n 是 m 右兄弟 C.n 是 m 左兄弟 D.n 是 m 祖先

2010上机题1. 输入两个字符串s和t，打印出t在s中的出现的位置，并输出出现的次数如输入：s=qwqwertqweqqqq，t=qw输出：1 3 532. 观察一个数的序列规律，1，2，3，4，5，6，8，9，10，12，15，16，18……现在输入一个数8（即上述序列中的第8个数），输出：9试编程实现。

注：上述序列皆是1，2，3，5，的倍数3.求二进制逆序如输入10，对应二进制数为1010，其逆序为0101，对应十进制输出为5（5即为10的逆序数）。

4.求满足条件n*n-m*m-n*m=1，且使m*m+n*n值最大的m，n，其中m，n的值都要小于k，k由用户输入。

5.已知一个数组如a【10】={1，2，3，4，5，6，7，8，9，0}，输入p，则右移p位，如输入3后，输出a【10】={8，9，0，1，2，3，4，5，6，7}，要求时间复杂度和空间复杂度尽量小。

6.已知一个斜三角：22 32 14 77 4512 34 37 2344 23 1534 5488从最左上角元素开始往右或往右下走，请问顺着哪条路所经过的值的总和最大，如可以有路线：22，32，34，23，54 ；22，12，44，34，88等等请求出满足值总和最大的那条线路。

2010上机原题答案毕竟回忆的，个别地方会有一点点的出入第六题没来得及做，第一题有点问题，大家自己调一下。

第一题#include<iostream.h>#include<iomanip.h>#include<math.h>#include<string.h>void main(){char s[70],t[100];int i=0,j,count=0,len;cout<<"输入两字符串:"<<endl; cin>>s;cout<<"输入第2个字符串："<<endl; cin>>t;len=strlen(t);while(s!='\0'){for(j=0;j<=len;j++){if(s[i+j]==t[j])j++;else break;}if(j==len+1){count++;cout<<i+1;}i++;}cout<<endl<<count<<endl; }第二题#include<iostream.h>#include<iomanip.h>#include<math.h>int fun(int n){while(n%2==0)n=n/2;while(n%3==0)n=n/3;while(n%5==0)n=n/5;if(n==1)return 1;else return 0;}void main(){int j=0,n,a[1500];long i;for(i=1;i<1000000;i++) { if(fun(i))a[j++]=i;}cout<<"输入n(n<=1500)："<<endl; cin>>n;cout<<a[n-1]<<endl;}第三题#include<iostream.h>#include<iomanip.h>#include<math.h>void main(){int i=0,m,j=0,n=0,a[100];cout<<"输入一个十进制数："<<endl; cin>>m;while(m!=0){a=m%2;m=m/2;i++;}while(j<i){n=n*2+a[j];j++;}cout<<"其二进制逆序数："<<endl<<n<<endl; }第四题#include<iostream.h>#include<iomanip.h>#include<math.h>void main(){int m,n,k,maxm,maxn,max=0;cout<<"输入k:"<<endl;cin>>k;for(m=0;m<=k;m++)for(n=0;n<=k;n++)if(n*n-m*n-m*m==1&&max<m*m+n*n){ max=m*m+n*n;maxm=m;maxn=n;}cout<<maxm<<""<<maxn<<endl;}第五题#include<iostream.h>#include<iomanip.h>#include<math.h>void main(){int p,i,j,r[10]={1,2,3,4,5,6,7,8,9,10},s[10]; cin>>p;for(i=0;i<=p-1;i++)s=r;for(j=p;j<=10;j++)r[j-p]=r[j];for(j=0;j<p;j++)r[10-p+j]=s[j];cout<<"左移后的结果："<<endl;for(i=0;i<10;i++)cout<<r<<setw(5);cout<<endl;}2007年A.1 递归方程编程。