计算机水平考试-程序员分类模拟题数据结构与算法(一).doc
说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。
程序员分类模拟题数据结构与算法(-) 综合知识试题 K对具有n个元索的顺序表(采用顺序存储的线性表)进行 _________ 操作，其耗时与n的大小无关。 A. 在第i(lWiWn)个元素Z后插入一个新元素 B. 删除第i(lWiWn)个元素 C. 对顺序表中的元素进行排序 D. 访问第i(lWiWn)个元素的前驱和后继 2、 若字符串s的长度为n(n>l)且其中的字符互不相同，贝Us的长度为2的子串右 ________ 个。 A・ n B・ n-l C・ n-2 D. 2 3、 栈的运算特点是后进先出。元索a、b、c、d依次入栈，则不能得到的出栈序列是 __________ A- a b c d B. c a b d C. d c b a D. b c d a 4、某循环队列的容量为M,队头指针指向队头元素，队尾指针指向队尾元素Z后，如图8-18所示则队列屮的元索数目为 _______________ (MOD表示整除取余运算)。 5、 设初始栈为空，s表示入栈操作，x表示岀栈操作，则 _________ 是合法的操作序列。 A・ sxxsssxxx B・ xxssxxss C- sxsxssxx D・ xssssxxx 6、 n个元索依次全部进入栈后，再陆续出栈并经过一个队列输出。那么， _________ 。 A. 元素的出队次序与进栈次序相同 储环队列指针示童图 队崔 A. rear-front B. front-rear re剖 I伽I 。 (M=8)，B. 元素的出队次序与进栈次序相反 C. 元素的进栈次序与进队次序相同 D. 元素的出栈次序与出队次序相反 7、 与单向链表相比，双向链表 ________ o A. 需要较少的存储空间 B.遍历元素需要的时问较短 C.较易于访问相邻节点 D.较易于插入和删除元素 8、若一个栈以向ftv [1. .n]存储，且空栈的栈顶指针top为n+l,则将元素x入栈的正确操作是A・ top=top+l； V[top]=x； C. top=top-l； V[top]=x； B. V[top]=x； top=top+l； D. V[top]=x； top=top-l； 9、 在执行递归过程吋，通常使用的数据结构是 _______ 。 A. 堆栈（stack） B.队歹J （queue） C・图（graph） D・ M （tree） 10、 设数组a[1..6, 0. .9]的元素以行为主序存放，每个元素占用一个存储单元，则数组元素a [3, 3]的地址为 ________ o A. a+23 B・ a+27 C・ a+39 D. a+35 IK若二维数组P[1..5, 0..8]的首地址为base,数组元素按行存储，且每个元素占用1个存储单 元，则元索P[3, 3]在该数组空间的地址为 _________________________ 。 A. base+13 B. base+16 C. base+18 D. base+21 丄2、釆用一维数组S存储一个n阶对称矩阵A的下三角部分（按行存放，包括主对角线）,设元素A[i] [j] 存放在S[k]中（i、j、k均从1开始取值），_&S[1]=A[1] [1],贝Uk与i、j的对应关系是 _____________ A. 例如，元素A⑶⑵存在S[5]中。 C. D. 13. _____________________________ 数组A[-5・・5, 0..8]按列存储。若第一个元索的首地址为丄00,且每个元索占用4个存储单元, 则元素A[2, 3]的存储地址为 o A. 244 B. 260 C・ 364 D・ 300 14. 若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于1,则该二叉树的 __________ o A.只有根节点无左予树 B.只有根节点无右子树 C.非叶子节点只有左子树 D.非叶子节点只冇右子树 15、 由关键字序列（12, 7, 36, 25, 18, 2 ）构造一棵二叉排序树（初始为空，第一个关键字作为根 节点插入，此后对于任意关键字，若小于根节点的关键字，则插入左子树屮，若大于根节点的关键字, 则插入右子树中，口左、右子树均为二叉排序树），该二叉排序树的高度（层数）为 _________ o A. 6 B. 5 C. 4 D・ 3 16. ____________________________________________ 对连通图进行遍历前设置所冇顶点的访问标志为false （未被访问），遍历图后得到一个遍历序 列，初始状态为空。深度优先遍历的含义是：从图中某个未被访问的顶点v出发开始遍历，先访问v 并设置其访问标志为true（已访问），同时将v加入遍历序列，再从v的未被访问的邻接顶点中选一个 顶点，进行深度优先遍历；若v的所有邻接点都已访问，则冋到v在遍历序列的直接前驱顶点，再进 行深度优先遍历，直至图屮所有顶点被访问过。 是图8-19的深度优先遍历序列。 A 17>在任意一棵非空的二叉树中，终端节点（叶子）的数目总是比具有两个孩子的非终端节点的数目 A.多0个 B.多1个 C.多2个 D.多3个 满二叉树的特点是每层上的节点数都达到最大值，因此对于高度为h（h>l）的满二叉树，其节点总数 为18。对非空满二叉树，由根节点开始，按照先根后了树、先左了树后右了树的次序，从1, 2, D・ 2h-l+l D・ 2i+2 3,・・•依次编号，则对于树中编号为i的非叶子节点，其右子树的编号为19 （高度为3的满二叉树如 20、数据结构中的树最适合用来表示 ________ 的情况。 A.数据元索有序 B.数据元索之间具冇多对多关系 C.数据元素无序 D.数据元素Z间具有一对多关系 21、二叉排序树或者是一棵空树，或者是具冇如下性质的二叉树：特其左子树非空，则左子树上所 有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、 右子树木身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 _____________ 遍历，可得到 一个节点元索的递壇序列。 A.前序（根、左、右） B.中序（左、根、右） C.后序（左、右、根） D.层序（从树根开始，按层次） 19> A・ 2i B. 2i-l C・ 2i+l 22、广度优先遍历的含义是：从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的 邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且''先被访问的顶点的邻接点〃先于''后 被访问的顶点的邻接点〃被访问，直至图中所冇己被访问的顶点的邻接点都被访问到。 __________ 是图 8的广度优先遍历序列。 A.1 2 6 3 4 5 B. 1 2 3 4 5 6 C. 1 6 5 2 3 4 D.1 6 4 5 2 3 23、对图8・22所示的二叉树进行屮序遍历（左子树、根、右子树）的结果是 二叉拥示竟图 A. 2 5 3 4 6 1 B. 2 5 3 4 1 6 C・ 2 6 5 4 1 3 D・ 2 6 4 5 3 1 若将图8-23（"所示的无向图改为完全图，则还需要增加24条边;图（b）的邻接矩阵表示 为25 （行列均以A、B、C、D、E为序）。 24、A. 1 B. 2 C・5 D・15 0 110 10 10 110 1 (a) 25、A. 0 1 0 0 (b) 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 _1 0 0 1 B. 0 无向图和有向图示意国 1110 0 0 110 1 0 0 110 c.0 0 1 1 0 0 0 0 10 1 0 0 0 10 0 0 0 0 0 0 0 0 26、对如图8・24所示的二叉树进行后序遍历(左子树、右子树、根节点)的结果是 _________ 二叉树示意图 A. 5 2 3 4 6 1 B. 5 2 3 4 1 6 C. 2 6 4 1 3 5 D・ 2 5 6 4 3 1 27、若线性表(24, 13, 31, 6, 15, 18, 8)采用散列(Hash)法进行存储和查找，设散列函数为 H(Key) =Key mod "，贝U构造散列表时发生冲突的元索为 _________ (其中的mod表示整除取余运算)。 A・24和13 B・6和15 C・6和24 D・18和8 28、 线性表采用顺序存储结构，若表长为m,且在任何一个合法插入位置上进行插入操作的概率相同, 则插入一个元素平均移动 ______ 个元素。 A. m-丄 B. m/2 C. m/2 + 1 D・ m 29、 两个递增序列A和B的长度分别为m和n(mVn),将两者归并为一个长度为m+n的递增序列时， ，归并过程中元素的比较次数最少。 A. 当A的最大元素大于B的最大元素时 B. 当A的最大元素小于B的最小元素时 C. 当A的最小元素大于B的最小元素时 D. 当A的最小元索小于B的最大元索时 30、对于n个元素的关键字序列{匕，k2, k },若将其按次序对应到一棵具有n个节点的完全二叉 树上，使得任意节点都不大于其孩子节点(若存在孩子节点)，则称其为小顶堆。根据以上定义， 是小顶堆。 21 B. 63 25 23 D. 31、采用哈希（或散列）技术构造查找表时，需要考虑冲突（碰撞）的处理，冲突是指 _______ A. 关键字相同的记录被映射到不同的哈希地址 B. 关键字依次被映射到编号连续的哈希地址 C. 关键字不同的记录被映射到同一个哈希地址 D. 关键字的数目超过哈希地址的数目 32、对于长度为的顺序存储的有序表，若采用折半查找（向下取整），则找到第5个元素需要与表 中的 __________ 个元素进行比较操作（包描与笫5个元素的比较）。 A・5 B・4 C・3 D・2 33、如果待排序序列中两个元索具冇相同的值，在排序前后它们的相互位置发生颠倒，则称该排序 算法是不稳定的。 ____________ 是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不 进行交换。 A.冒泡排序 B.希尔排序 C・快速排序 D.简单选择排序 34、用二分法来检索数据，最确切的说法是 ________ A. 仅当数据随机排列时，才能正确地检索数据 B. 仅当数据有序排列时，才能正确地检索数据 C. 仅当数据量较大时，才能冇效地检索数据 D. 仅当数拯量较小时，才能有效地检索数据 35、若原始数据序列（23, 4, 45, 67, 12, 8, 19, 7）釆用直接插入排序法（顺序地将每个元素插 入到它之前的适当位置）排序，则进行完第4趟后的排序结果是 ___________________ 。 A. 4, 8, 45, 23, 67, 12, 19, 7 B. 4, 7, 8, 12, 23, 45, 67, 19 C・ 4, 12, 8, 19, 7, 23, 45, 67 D・ 4, 12, 23, 45, 67, 8, 19, 7 案例分析试题 试题一 阅读以下说明和C语言函数，回答问题。 ［说明］ 函数sort（NODE*head）的功能是：用冒泡排序法对单链表中的元素进行非递减排序。对于两 个相邻节点屮的元素，若较小的元素在后而，则交换这两个节点中的元素值。其中，head指向链表 的头节点。排序时，为了避免每趟都扫描到链表的尾节点，设置一个指针endptr,使其指向下趟扫 描需要到达的最后一个节点。例如，对于图8-25 （a）所示的链表进行一趟冒泡排序后，得到图8-25 （b） 所示的链表。 endplr endptr (1» 琏表 链表的节点类型定义如下： typedef Struet Node { int data； struct Node *next； }NODE; [C语言函数] void sort(NODE *head) { NODE *ptr, *preptr, *endptr； int tempdata； ptr=head- >next ； while 36 /*查找表尾节点*/ ptr=ptr- >next ； endpt r=ptr； / ★令endpt r指向表尾节点* / ptr= 37 ； while(ptr!=endptr) { while( 38 ) { — if (ptr- >data>ptr- >next- >data) { tempdata=ptr- >data； /*交换相邻节点的数据*/ ptr- >data=ptr- >next->data ； ptr- >next- >data=tempdata ； } preptr=_39_； ptr=ptr- >next ； } endptr=_40_； ptr=head- >next ； 试题二 阅读以下说明和c程序，回答问题。 [说明] 卜•面的程序用Dole Rob算法生成N阶（N为奇数）魔方阵（各行、列、对角线数字Z和相等）。该 算法的过程为：从1开始，按如下方法依次插入各自然数，直到N2为止。 ① 在笫一行的正中插入1。 ② 新位置应当处于最近插入位置的右上方，若该位置已超出方阵的上边界，则新位置取应选列 的最下一个位置；若超出右边界，则新位置取应选行的最左一个位置。 ③ 若最近插入的元素是N的整数倍，则选同列的下一行位置为新位置。 例如，3阶魔方阵如下所示： 8 16 3 5 7 4 9 2 [C程序] #include #include・ h> #define SIZE 50 main46
{
int row, col, n, value； int a[SIZE+l] [SIZE+1] ;
/*不使用下标为0的元素★/
printf （"请输入要输出魔方阵的阶数n（奇数，V%d）：ni, SIZE.; scanf（H %dH, &n）；
if (! (n%2) | | n41 ) { printf ( ”轴入数据有误! \n"); exit47； }
row=l； col=(n+l)/2； value=l； while (value<=_42_) {
a [row] [col]=value； 八计算下一位置*/ if(value%n!=0){ row--； 43 ； if (row；
if (col>n) 44 ；
}
else row++； value= 45 ； } 一
printf ("\n%d阶魔方阵如下所刀七\n\nn z n)； for (row=l ； row<=n； row++) {
for (col = l ； col<=n； col + +)
printf("%5d"z a[row][col])； printf(n\nH)；
阅读以下说明和c函数, 回答问题。 试题三
[说明]
计算机在处理算术表达式时,首先将其转换为后缀表达式。例如,表达式''46 + 5* (120-37)" 的后缀表达式形式为''46 5 120 37- * +〃。
计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符， 则从栈屮弹出相关运算对象进行计算，并将运算结果压入栈屮。重复以上过程，直到后缀表达式扫描 结束。例如，后缀表达式''46 5 120 37 - * + 〃的汁算过程如下。
① 依次将46、5、120> 37压入栈中。
② 遇到、'.〃，取出37、120,计算120-37 = 83,将其压入栈中。 ③ 遇到'"〃，取出83、5,计算5x83=415,将其压入栈中。
④ 遇到'' + 〃，取出415、46,计算46+415=461,将其压入栈中。 ⑤ 表达式结束，则计算过程完成。
函数computing (char expt [] , int *result)的功能是基于栈计算后缀形式的表达式(以 串形式存入字符数组expr)的值，并通过参数result返回该值。函数的返回值为-1/0,分别表示表 达式有/无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运 算符仅包含加('' + 〃)、减(''-〃)、乘("〃)、除(、'\〃)。
函数computing中所用栈的基本操作的函数原型说明如下。 void InitStack (STACK *s):初始化栈。
void Push (STACK *sz int e):将一个整数压栈，栈屮元素数目增1。 void Pop (STACK *s):栈顶元素出栈，栈中元素数目减
int Top (STACK s)：返冋非空栈的栈顶元素值，栈屮元素数口不变。 int IsEmpty (STACK s):若s是空栈，则返回1；否则返回0。 [C函数]
int computing (char expr [] , int *result) {
STACK s; int tnum, a, b； char *ptr ； InitStack (&s)；
ptr=expr； pstr
while (*ptr! = 1\01 ) /*字符*旨针指向后缀表逆式串的第一个字符*/
{
if(*ptr==' ') { /*当前字符是空格*/
46 ； /*字符指针指向下一字符* / continue； }
else if (isdigit(*ptr)) {
/*当前字符是数字，则将该数字开始的数字串转换为数值*/
tnum= 47 ； while (*ptr>= ' 0 * && *ptr<= * 9 1 ) { tnum=tnum *10+ 48 ; ptr++； } push( 49 )；
} else /法当前字符是运算符或其他符号* /
if (*ptr==【+i||*ptr=='-'||*ptr== if(!IsEmpty(S)){
a=Top (s) ; Pop (&s) ; /*取运算符的第二个运算数*/ if(!IsEmpty(S)){ b=Top(s)； Pop(&s)；
八取运算符的第一个运算数*/
}
else return-1； }
else return -1； switch (*ptr) { case 1 + f ： case 1 - 1 ： case 1 + f ： case 1/1 ： }
Push(&S, b+a)； break； else
Push(&s, b-a)； break； return ・ -1 ；
Push(&s, b*a)； break； 決字符指针指向下一字符*/ ptr++； }/*whil/Push(&s, b/a)； break；
e*/ if (IsEmpty(s)) return -1； else {
50 =Top(s) ； Pop (&s) ； /*取运算结果*/ if (!IsEmpty(s)) return -1； return 0； -}
试题四
阅渎以下说叫和c函数，回答问题。
[说明]
已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组节点结构 及数组Ht的定义如下：
#define MAXLEAFNUM 30 Struct node{ char ch； char *pstr； int parent； int lchild, rchiid; };
Struct node Ht [2 *MJ\XLEAFNUM];
该二叉树的n个叶了节点存储在下标为1.〜n的Ht数组元素中。例如，某二叉树如图8-26所示， 其存储结构如图8-27所示，其屮，与叶子节点a对应的数组元素下标为1, a的父节点存储在Ht [5],
表示为Ht [1] .parent = 5o [7] .parent = O表示7号节点是树木艮,Ht [7] .1 child=3> Ht [7] . rchild=6分别表示7号节点的左孩子是3号节点、右孩子是6号节点。
如果用''0〃或''1〃分别标识二叉树的左分支和右分支如图8-26所示，从根节点开始到叶子节点 为止，按所经过分支的次序将相应标识依次排列，可得到一个0、1序列，称之为对应叶子节点的编 码。例如，图8-26中a、b、c、d的编码分别是100、101、0、llo
函数LeafCode (Ht [] , n)的功能是：求解存储在Ht屮的二叉树屮所冇叶子节点(n个)的编码, 叶子节点
存储在Ht [1]〜Ht [n]中，求岀的编码存储区由对应的数组元素pstr域指示。
下标 ch
1 2
3 .4
purait 5 5 7 6 6 7 D
lehild
rchild 0 (1 0 0 2 4 6
b c d
0 0 0 1 5 3
二叉树
5 6 7
二叉树存储结构
函数LeafCode从叶子到根逆向求叶子节点的编码。例如，对图8-26中叶子节点a求编码的过程 如
pr
pc
图8・28所示。
从叶子到根求节点編码示童图
[函数]
typedef enum Status {ERROR, OK} Status; Status LeafCode (Struet node Ht [] z int n) {
int pc, pf；
int i, start；
char tstr [31]={1\01)；
for(i=l； 51 ； i++) {
start=29；
pc = i； pf=Ht [i]・parent； while(Pf!= 52 ) { if( 53 • lchiid==pc) tstr [--start] = * 0'； else
tstr [-start] = 11'； pc= 54 ； pf=Ht[Pf]・parent；
}
Ht[i] >pstr=(char*)malloc(31-start)； if(!Ht[i]・pstr)return ERROR； strcpy(Ht[i]• pstr, 55 ;
} — return OK；
}
试题五
回答问题。 阅读以下说明和c语言函数,
［说明］
已知包含头节点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress (NODE *head)的功能是去掉其中重复的元素，使得链表屮的元素互不相同。
处理过程中，当元素重复出现时，保留元素第一次岀现所在的节点。 图8-29 (a)、(b)是经函数compress61处理前后的链表结构示例图。
曲d二H 23| 4H351 八]
处理前•链表结构
h閃dfj肆耳一H门I 一H 十匡IF
co处理后链表结构
'链表结构
链表的节点类型定义如下： typedef struct Node { int data；
struct Node *next； }NODE;
[C语言函数]
void compress(NODE *head) {
NODE *ptr, *q； ptr= 56 ; / *取得第一个元素节点的指针★ / while ( 57 && ptr- >next) { q=ptr - >next ； while (q && 58 ) {/*处理重复元索*/
59 =q - >next ； free(q);
q=ptr- >next ； } _60_=ptr- >next ； } /*end of while*/ } /*end of compress*/
试题六 阅读以下说明和流程图，填补流程图中的空缺。
［说明］
卜•面流程图的功能是：在已知字符串A中杳找特定字符吊B,如杲存在，则输出B吊首字符在A吊 中的位置,否则输出-1。设串A由n个字符A61、A62、.・・、A(n-l)组成，串B由m个字符B61、B62、.・.、 B(m-l)组成，其中n^m>Oo在串A中查找串B的基本算法如下：从串A的首字符A61开始，取子串 A61A62...i (m-1)与串B比较;若不同，则再取子串A62A69..A(m)与串B比较，以此类推。
例如,字符串''CABBRFFD"中存在字符子串、'BRF〃 (输出3),不存在字符子串''RFD"(输出-1)。 在流程图中，i用丁访问申A中的字符(i = 0, 1,・・・，n-1) , j用丁访I可吊B中的字符(j =0, 1,・・・, m-1) o 在比较A(i) A(i + l)・・A(i+m-l)与B61B62...B (m-1)时，需要对A⑴与B61> A(i+1)与 B62、••.、A(i + j)与B(j)、•••逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，以此 类推。
［流程图］
木题流程图如图8-30所示。
流程图
试题七
阅读以下说明和流程图，填补流程图中的空缺。
［说明］
假设数组A中的各元索A66, A6 7, ・・.，A(M)已经按从小到大排序(M^l);数组E中的各元索B66, B67, B(N)也已经按从小到大排序(N^l) o执行卜•血的流程图后，可以将数组A与数组B中所有 的元素全都存入数组C屮，冃按从小到大排序(注意：序列屮相同的数全部保留并不计排列顺序)。例 如，设数组A中有元
素：2, 5, 6, 7, 9；数组B中有元素2, 3, 4, 7；则数组C中将有元素：2, 2,
FalAe
False
3, 4, 5, 6, 7, 7, 9o
［流程图］
木题流程图如图8-31所示。
试题八 阅读以下说明和流程图，填补流程图中的空缺。
［说明］
某单-位动态收集的数据屮常包含重复的数据，所以需要进行处理，使得重复的数据仅出现一次。 下面流程图的功能是：在n(n>l)个数据D2,氏中，选出其中所冇不重复的k个数据，置于原 来前k个数据的位置上。
(开始)
⑶一 C⑴
汁—i k+1-k
汁I k+1-k
£6}-C(k) £71-C(k)
j+—j
i—i k-l—k
流程
该流程图的算法如门第1个数据必然被选出，然后从第2个数据开始，逐个考察其余的数据。 假设D. D“・・・，Djm^l)是已经选出的、不重复的数据,则对于数据D'mViWn),将其依次与人, ・・•，R
进行比较，若没有发现与之相同者，则D,被选出并置于D*的位置上；否则对D,不做处理。 例如，如下10个数据：
(n=10) 5, 2, 2, 7, 4, 4, 7, 1, 9, 1 经过上述算法处理后的结果为： 5, 2, 7, 4, 1, 9 (k=6) ［流程图］
木题流程图如图8 - 32所示。
处理遊站D［i］
E 1 (1)
i: 丐 1
主控
处理数据D［i］
「循环结束
< 一
_____ 」 F ______
输出处理结呆
遞冋
流程
注：循环开始的说明按照''循环变量名：循环初值，循环终值，增量〃格式描述。
答案：
综合知识试题
1> D
［解析］对具有n个元素的顺序表访问第i(lWiWn)个元素的前驱和后继，其耗吋与n的大小无关。
2、 B ［解析］若字符审s的长度为n(n>l)且其中的字符互不相同，贝b的长度为2的了吊有nJ个。 3、 B
［解析］首先可用得到出栈序列dcba,如果毎个元素入栈后即出栈，则可得abed,若c位于栈顶，而 ab在栈中,则可得cbad,但不能得到cabdo
4、 C
［解析］队列容量为M时，队头指针front和队尾指针rear的值在0〜M-丄之间循环，当rear>front 口寸，丿匸素数口为匕ear-f ront；当rearVf ront吋，7匸素数口为rear-f ront+M。所以，队歹lj1117U 索数廿为 (rear-front+M)MOD M。 5、 C
［解析］本题考查数据结构巾栈的基本知识。栈的特点是后进先出。对于一个关于初始为空的栈的操 作序列，要求序列中任何一个操作之前，入栈操作的次数要大于等于出栈操作的次数。操作序列 SXSXSSXX满足条件。 6、 B
［解析］栈是先进后出的线性表，n个元素全部进入栈后再依次出栈，则得到原序列的逆序。队列是 先进先出的线性表，元素的进入次序与输出次序相同，因此，n个元素先后经过栈和队列，得到的序 列与进入栈的序列相反。 7、 C
［解析］本题考查链表存储结构的基本特点。在单向链表中只能沿一个方向进行访问节点，而在双向 链表中既可以向前遍历，也可以向后遍历。因此，双向链表较易于访问相邻节点。 8、 C
［解析］空栈的栈顶指针top为n+1,说明栈顶指针随着元素入栈而减小，随着元素岀栈而增加，所 以元素x入栈的正确操作是top=top-l； V ［top］ =Xo 9、 A
［解析］在执行递归过程时，通常使用的数据结构是堆栈，耍求先调用后返回。 丄0、A
［解析］以行为主序存储，元素a［3, 3］之前有23个元素，所以其相对于数组起始地址的偏移量为23, 地址为a+23o 11> D
［解析］数组空间首地址为base,所以，元素P［l, 0］的存储地址为base,按行存储时，P［3, 3］ Z前存储了2x9 + 3个元素，因此P［3, 3］在该数组空间的地址为base + 21o 12、 D
［解析］子题考查特殊矩阵的压缩存储。对称矩阵下三角的兀密按行存储时，对于元素A［i］ ［j］,其 前面的元素数目为 l+2+...+ i-l + j-l = i(i-l)/2 + j-l,因此元索 A［i］ ［j］存储在 S ［i(i-l)/2 + j］ 中。 13、 B ［解析］数组按列存储时，存储在A ［2, 3］之前的元素个数为11x3 + 7,因此，其存储地址为 100+40x4=260。 14、 D
［解析］若二叉树的前序遍历序列与中序遍历序列相同，说明二叉树的根节点没有左了树，以此类推, 二叉树所冇节点都没冇左子树，非叶子节点只冇右子树。 15、 C
［解析］根据题意，由关键字序列(丄2, 7, 36, 25, 18, 2 )构造的二叉排序树的高度应该为4层， 第一层为12,第二层为7和36,第三层为2和25,最后一层为丄8。 16、 A
［解析］根据图屮的邻接关系，顼点4后应该就是顶点6,所以A选项正确。 17> B
［解析］在任意一棵非空的二叉树中，终端节点(叶子)的数目总是比具有两个孩子的非终端节点的数 口多 1 个。18、C 19、 C
［解析］本题考杳数据结构中二叉树的基本知识。满二叉树的第［层(树根)有1个节点，第二层有2个 节点，第三层冇4个节点，以此类推，第h层冇2h-l个节点。总节点数为20 + 21 + 22+...+2h-l = 2h-lo 依题意，显然对非空满二叉树中的节点i的左子树编号为2i,右子树编号为2i + l0
20、 D
［解析］本题考查数据结构屮树的基本知识。数据结构屮的树最适合用来表示数据元素Z间具冇一对 多关系的情况。 21> D
［解析］中序遍历二叉树的过程为：若二叉树为空，则进行空操作；否则中序遍历根的左子树：访问 根节点；中序遍历根的右了树。显然，对一棵非空的二叉排序树进行中序遍历，可得到一个节点元素 的递增序列。 22、 A ［解析］根据题口描述，对题屮图进行广度优先遍历吋，先访问顶点1,由于2和6是顶点1的邻接顶点, 因此接下來应访问顶点2或顶点6,若先访问顶点2,此吋的访问序列为1 2 6;反之，访问序列则为 16 2,然后访问顶点2、6（或6、2）的邻接顶点。因此，最后的遍历序列为1 2634 5、126 35 4、16254 3 或1 6 2 4 5 3。 23、 D ［解析］中序遍历的操作过程是：若二叉树为空，则进行空操作；否则先选小序遍历根的左子树，然 后访问根节点，最后中序遍历根的右子树。因此，本题中的二叉树进行中序遍历，可以得到序列为2 6 4 5 3 24、 C 25、 D ［解析］本题考查的是图的概念及存储结构。含有11个顶点的无向完全图共有n（n-l）/2条边。图的矩 阵表示法利用一个炬阵来表示图屮顶点之间的关系。根据邻接矩阵的特点可知D选项符合要求。 26、 C ［解析］本题考查的是二叉树的遍历运算。后序遍历是指先遍历左了树，再遍历右了树，最后访问根 节点。所以，本题后序遍丿力结果应为264135c 27、 A ［解析］根据散列函数可得H（24）=H（13）=2,所以24和12两个元素冲突。 28> B
［解析］线性表采用顺序存储结构，若表长为m,且在任何一个合法插入位置上进行插入操作的概率 相同，则插入一个元素平均移动ni/2个元素。 29、 B ［解析］若A的最大元素小于B的最小元素，则只需要比较m次，这吋归并过程屮元素的比较次数最少。 30、 D ［解析］木题考查排序方法中堆排序的基础知识。四个选项中只有选项D符合小顶堆的定义。 31、 C
［解析］采用哈希（或散列）技术构造查找表时，需要考虑冲突（碰撞）的处理，冲突是指关键字不同的 记录被映射到同一个哈希地址。 32、 B ［解析］本题考杳折半（二分）查找。折半查找是指首先将待查找的元素与表中的中间元素比较（第6 个元素），若相等，则找到，若大于屮间位置元素，则下一步到后半个子表进行折半查找，否则，下 一步到前半个子表进行折半查找。因此，要找表中的第5个元素，需要与第6、3、4和5个元素依次比 较，查找成功，所以共比较4次。 33> A
［解析］木题考查排序算法。冒泡排序是稳定的排序方法，它比较相邻的元素，将较大者交换到后面, 对于值相同的元素，则无须交换。 34、B
［解析］对于二分查找方法，只有元素进行有序排列时，才能正确地进行查找。 35^ D
［解析］本题考查的是插入排序法。其实现方法是：在插入第i个记录吋，前i-l个数已经排好序，这 时将记录的关键字ki依次与关键字ki-1, ki-2, kl进行比较，从而找到Ri应该插入的位置。
案例分析试题 试题一
36、ptr- >next ptr
40^ preptr
37、head- >next
38、ptr ! = endptr,或其他等彳介丿孩式
39、
[解析]
从⑴ 处代码中口J知ptr最后应该指向表尾节点。所以⑴ 处应为ptr->nexto进彳亍钉泡排序 时，不断调整元素的位置，最终使最大元素放到表的最后，所以（2）处应为head->nexto （3）处的 循环条件应该是扫描的节点，不是最后一个节点，所以（3）处应为ptr ! =endptro ptr每向后修改 一次，preptr就要修改一次，所以（4）处应为ptr, （5）处应为preptro 试题二 41、n>SIZE,或其等价表示 42^ n*n 43、col + + ,或+ + col,或col=col + l,或 其等价表示 44、col-=n,或col = l,或其等价表示 45、 value+1,或其等价表示 [解析]程序中空（1）处判断n的合法性，n需为奇数，矩阵规模应不超过SIZE2o所以（1）处应为n >SIZE,或其等价表示。将数值填入方阵的语句为''a [row] [col] =value ；,该语句在循环中， 循环条件为''value<=n*n^,所以（2）处应填入55〃。对于3阶魔方阵，1填入第1行第2列，2填 入第3行第3列，3填入第2行第1列，其余位置按照算法步骤类推。所以（3）处填入、'col + + 〃或其等价 形式，（4）处填入= 或、'col-=n〃。程序中，本次填入的数值为value的值，下一次要填入的 数值为vahle加1,因此,空（5）处应填入''value+lz/。
试题三
46、 ptr+ + ,或++ptr, SKptr=ptr+l,或其等彳介表示 47、0, ^Ktnum=0 48、*ptr-48, 或*ptr- 'OS 或-其等价表示 49、&s, tnum 50、 *result
[解析]由于后缀表达式以字符串方式存储且以空格分隔符号（数值、运算符），因此遇到空格字符吋, 指向表达式中字符的指针ptr应增加丄指向后续字符，所以（1）处应填入、'ptr++〃或其等价形式。 匸num的初始值应为0,因此，空（2）处应填入''0〃，空（3 ）所在表达式将数字字符转换为数值，即空 （3） 处填入''*ptr-48/zo空（4）处用于将转换所得的数值tnum压入栈项，根据题目屮Push的原型 ''void Push （STACK*sz int e） 〃，调用时第一个实际参数是STACK类型变量的地址，第二个实 际参数是一个整数，因此，空（4）处填入''&s,匸num"。由于函数computing （char expr [] z int result）通过参数result返回该表达式的值，因此需要将存在栈顶的运算结果赋值给result指向 的整型变量，即空（5）处填入'"result"。
试题四
51> i<=n,或其等价形式 55> tstr+start^<[start]
52、
53> Ht [pf ],或（* （Ht+pf） ）
54、pf
[解析]题中已指出该二叉树的n个叶了节点存储在卜•标为1到n的Ht数组元素中，同时举例说明父节 点编号为0的节点是树根节点。所以，（1）处应为、'iV=n〃。而到达根即父节点为0时，所以（2）处为 ''0〃。pc用于指出树中的节点，pf则用于指出pc所对应节点的父节点，所以（3）处应为''Ht [pf ]", （4） 处应为''pf 〃 o根据tstr的作用,strepy函数的实参应该是''tstr+start,z或 ''&tstr [start] 〃 ,所以（5）处应该为 ''tstr+start^^''[start]"。
试题五
56、head>next ptr- >next
57、ptr
58、ptr->data==q-或其等仔丫形式
59>
60、ptr
[解析]本题考查的是对链表的查找、插入和删除等运算。耍找到重复的兀素并将其删除而使各兀素 互不相同。我们可以顺序遍历链表，比较逻辑上相邻的两个元索是否相同，如果相同则删除后一个元 素，以此类推。代码如下：
VOid Compress（NODE *head） {
NODE *ptr, *q； ptr=head->next; /*取得第一个元索节点的指针*/
while (ptr && ptr- >next) q=ptr- >next ；
while (q && ptr ->data==q>data) {
ptr- >next=q- >next ； free(q);
q=ptr- >next ；
}
ptr=ptr- >next ； } /*end of while*/ } /*end of compress*/
{
/*处理重复元素*/
试题六
61、j+l 65、 -1
62、i + 1
63、
64、
[解析]依题意，在已知字符串A屮查找特定字符串B,基本算法如下：从串A的首字符A(0)开始，取 子串A(0)A(l)..A(m-l)与串B比较;若不同，则再取子串A(l)A(2)..A(m)与串B比较,以此类推。 我们可以采用两重循环來实现。初始时，i与j都设为0, i范围为0至n-l, j范围为比较A(i + j) 与B(j)是否相等，在循环过程中只耍存在一个j使得A(i + j )不等TB(i),则退出本次循环，i + 1后 重新进行遍历。如果最后i>n-m则说明不存在B字符串。否则，返冋B字符串的位置。
试题七
66、 A(i) 74、
67、A(i) 73、
68、B (j )
69、
70、
71、B (j )
72、
[解析]本题中，i、i、k是数组A、B、C的下标，初始时都应该是1。所以(1)处应为丄。为了实现 升序排列,将A(i)与B(j)进行比较后,如果A(i)WB(j),那么应该将A(i)-C(k)。所以⑵处 为A(i)。如果A(i)>B(j),则应将B(j)->C(k) o所以(3)处应为B(j) o通过判断i>M是否成立 来比较数组A是否已经取完。如果i>M,则表示数组A屮的元素已经全部取击，需要将数组B屮剩余的 元索逐个移入C(k) o因此，空(4)处应填i,空(6)处应填B(j) o对于数组B处的元索何时移完，需 要判断j>N是否成立。因此,空(8)处应填j。同样,空(3)处将B(j)存入C(k),直到j>N时数组B 屮的元素取完。此时，需要将数组A屮剩余的元素逐个移入C(k),直到i>M时全部完成。因此，空
(5) 处应填j,空(7)处应填A(i),空(9)处应填i。
试题八
75>
76、
77>
78、 D[m+1]
79、m^-m+1或-其等价形式
[解析]在流程图中，初始时应将m设置为1,(丄)处应为1,对于n个数据(n>l)而言，接着应逐个 考查D[2], D[n]的内容，因此循环应该对i=2, n, 1进行，所以(2)处应为2。考查D[i]时， 需要将其分别与D[m] , D[m-1] , D[l]逐个比较，所以循环应对1, 进行，所以⑶处 应为当比较过程中发现重复时，则不做处理，若没有重复，则应将D[i]存入D[m+1],所以(4) 处应为D [m+1],然后，将重复计数器m加：L,所以(5)处应为m—m+lo
本文来源：https://www.wddqw.com/doc/8edc676eab956bec0975f46527d3240c8447a103.html