1、数据结构与算法练习试卷 1及答案与解析 1 对具有 n个元素的顺序表 (采用顺序存储的线性表 )进行 _操作，其耗时与 n的大小无关。 A在第 i(1in)个元素之后插入一个新元素 B删除第 i(1in)个元素 C对顺序表中的元素进行排序 D访问第 i(1in)个元素的前驱和后继 2 若字符串 s的长度为 n(n 1)且其中的字符互不相同，则 s的长度为 2的子串有_个。 A n B n-1 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 设初
2、始栈为空， s表示入栈操作， x表示出栈操作，则 _是合法的操作序列。 A sxxsssxxx B xxssxxss C sxsxssxx D Xssssxxx 5 n个元素依次全部进入栈后，再陆续出栈并经过一个队列输出。那么， _。 A元素的出队次序与进栈次序相同 B元素的出队次序与进栈次序相反 C元素的进栈次序与进队次序相同 D元素的出栈次序与出队次序相反 6 与单向链表相比，双向链表 _。 A需要较少的存储空间 B遍历元素需要的时问较短 C较易于访问相邻节点 D较易于插入和删除元素 7 若一个栈以向量 V1n存储，且空栈的栈顶指针 top为 n+1，则将元素 x入栈的正确操作是 _。 A
3、 top=top+1； Vtop=x； B Vtop=x； top=top+1； C top=top-1； Vtop=x； D Vtop=x； top=top-1； 8 在执行递归过程时，通常使用的数据结构是 _。 A堆栈 (stack) B队列 (queue) C图 (graph) D树 (tree) 9 设数组 a16， 09的元素以行为主序存放，每个元素占用一个存储单元，则数组元素 a3， 3的地址为 _。 A a+23 B a+27 C a+39 D a+35 10 若二维数组 P15， 08的首地址为 base，数组元素按行存储，且每个元素占用1个存储单元，则元素 P3， 3在该数组
4、空间的地址为 _。 A base+13 B base+16 C base+18 D base+21 11 数组 A-55， 08按列存储。若第一个元素的首地址为 100，且每个元素占用 4个存储单元，则元素 A2， 3的存储地址为 _。 A 244 B 260 C 364 D 300 12 若二叉树的前序遍历序列与中序遍历序列相同且树中节点数大于 1，则该二叉树的 _。 A只有根节点无左予树 B只有根节点无右子树 C非叶子节点只有左子树 D非叶子节点只有右子树 13 由关键字序列 (12， 7， 36， 25， 18， 2)构造一棵二叉排序树 (初始为空，第一个关键字作为根节点插入，此后 对于
5、任意关键字，若小于根节点的关键字，则插入左子树中，若大于根节点的关键字，则插入右子树中，且左、右子树均为二叉排序树 )，该二叉排序树的高度 (层数 )为 _。 A 6 B 5 C 4 D 3 14 在任意一棵非空的二叉树中，终端节点 (叶子 )的数目总是比具有两个孩子的非终端节点的数目 _。 A多 0个 B多 1个 C多 2个 D多 3个 15 数据结构中的树最适合用来表示 _的情况。 A数据元素有序 B数据元素之间具有多对多关系 C数据元素无序 D数据元素之间具有一对多关 系 16 二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：特其左子树非空，则左子树上所有节点的值均小于根节点的值；
6、若其右子树非空，则右子树上所有节点的值均大于根节点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 _遍历，可得到一个节点元素的递增序列。 A前序 (根、左、右 ) B中序 (左、根、右 ) C后序 (左、右、根 ) D层序 (从树根开始，按层次 ) 17 若线性表 (24， 13， 31， 6， 15， 18， 8)采用散列 (Hash)法进行存储和查找，设散列函 数为 H(Key)=Key mod 11，则构造散列表时发生冲突的元素为 _(其中的mod表示整除取余运算 )。 A 24和 13 B 6和 15 C 6和 24 D 18和 8 18 线性表采用顺
7、序存储结构，若表长为 m，且在任何一个合法插入位置上进行插入操作的概率相同，则插入一个元素平均移动 _个元素。 A m-1 B m/2 C m/2+1 D M 19 两个递增序列 A和 B的长度分别为 m和 n(m n)，将两者归并为一个长度为m+n的递增序列时， _，归并过程中元素的比较次数最少。 A当 A的最大元素大于 B的最大元素时 B当 A的最大元素小于 B的最小元素时 C当 A的最小元素大于 B的最小元素时 D当 A的最小元素小于 B的最大元素时 20 采用哈希 (或散列 )技术构造查找表时，需要考虑冲突 (碰撞 )的处理，冲突是指_。 A关键字相同的记录被映射到不同的哈希地址 B关
8、键字依次被映射到编号连续的哈希地址 C关键字不同的记录被映射到同一个哈希地址 D关键字的数目超过哈希地址的数目 21 对于长度为 11的顺序存储的有序表，若采用折半查找 (向下取整 )，则找到第 5个元素需要与表中 的 _个元素进行比较操作 (包括与第 5个元素的比较 )。 A 5 B 4 C 3 D 2 22 如果待排序序列中两个元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。 _是稳定的排序方法，因为这种方法在比较相邻元素时，值相同的元素并不进行交换。 A冒泡排序 B希尔排序 C快速排序 D简单选择排序 23 用二分法来检索数据，最确切的说法是 _。 A仅当数
9、据随机排列时，才能正确地检索数据 B仅当数据有序排列时，才能正确地检索数据 C仅当数据量 较大时，才能有效地检索数据 D仅当数据量较小时，才能有效地检索数据 24 若原始数据序列 (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 25 阅读以下说
10、明和 C语言函数，回答问题。 说明 函数 sort(NODE*head)的功能是：用冒泡排序法对单链表中的元素进行非递减排序。对于两个相邻节点中的元素，若较小的元素在后面，则交换这两个节点中的元素值。其中， head指向链表的头节点。排序时，为了避免每趟都扫描到链表的尾节点，设置一个指针 endptr，使其指向下趟扫描需要到达的最后一个节点。例如，对于图 8-25(a)所示的链表进行一趟冒泡排序后，得到图 8-25(b)所示的链表。链表的节点类型定义如下： typedef Struet Node int data； struct Node *next； NODE; C语言函数 void sor
11、t(NODE *head) NODE *ptr, *preptr, *endptr; int tempdata; ptr=head- next; while (1) /*查找表尾节点 */ ptr=ptr- next; endptr=ptr; /*令 endptr指向表尾节点 */ ptr= (2) ; while(ptr!=endptr) while( (3) ) if(ptr- data ptr- next- data) tempdata=ptr-data; /*交换相邻节点的数据 */ ptr- data=ptr- next- data; ptr- next-data=tempdata;
12、 preptr= (4) ； ptr=ptr- next; endptr= (5) ; ptr=head- next; 26 阅读以下说明和 C程序，回答问题。 说明 下面的程序用 Dole Rob算法生成 N阶 (N为奇数 )魔方阵 (各行、列、对角线数字之和相等 )。该算法的过程为：从 1开始，按如下方法依次插入各自然数，直到 N2为止。 在第一行的正中插入 1。 新位置应当处于最近插入位置的右上方，若该位置已超出方阵的上边界，则新位置取应选列的最下一个位置；若超出右边界，则新位置取应选行的最左一个位置。 若最近插入的元素是 N的整数倍，则选同列的下一行位置为新位置。 例如， 3阶魔方阵如
13、下所示： 8 1 6 3 5 7 4 9 2 C程序 #include stdio.h #include stdlib.h #define SIZE 50 main( ) int row, col, n, value; int aSIZE+1SIZE+1; /*不使用下标为 0的元素 */ printf(“请输入要输出魔方阵的阶数 n(奇数 , %d):n=“, SIZE); scanf(“%d“, if(!(n%2) | n 1 | (1) ) printf(“输入数据有误 !n“); exit(0); row=1; col=(n+1)/2; value=1; while(value = (
14、2) ) arowcol=value; /*计算下一位置 */ if(value%n!=0) row-; (3) ; if(row 1)row=n; if(col n) (4) ; else row+; value= (5) ; printf(“n%d阶魔方阵如下所示： nn“, n); for(row=1; row =n; row+) for(col=1; col =n; col+) printf(“%5d“, arowcol); printf(“n“); 27 说明 计算机在处理算术表达式时，首先将其转换为后缀表达式。例如，表达式“46+5*(120-37)”的后缀表达式形式为 “46 5
15、 120 37- * +”。 计算后缀表达式时，从左至右扫描后缀表达式：若遇到运 算对象，则压入栈中；遇到运算符，则从栈中弹出相关运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如，后缀表达式 “46 5 120 37 - * +”的汁算过程如下。 依次将 46、 5、 120、 37压入栈中。 遇到 “-”，取出 37、 120，计算 120-37=83，将其压入栈中。 遇到 “*”，取出 83、 5，计算 583=415，将其压入栈中。 遇到 “+”，取出 415、 46，计算 46+415=461，将其压入栈中。 表达式结束，则计算过程完成。 函数 com
16、puting(char expt， int *result)的功能是基于栈计算后缀形式的表达式 (以串形式存入字符数组 expr)的值，并通过参数 result返回该值。函数的返回值为 -1/0，分别表示表达式有 /无错误。假设表达式中仅包含数字、空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含加 (“+”)、减 (“-”)、乘 (“*”)、除(“”)。 函数 computing中所用栈的基本操作的函数原型说明如下。 void InitStack(STACK *s)：初始化栈。 void Push(STACK *s, int e)：将一个整数压栈，栈中元素数目增 1。 void Po
17、p(STACK *s)：栈顶元素出栈，栈中元素数目减 1。 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( ptr=expr; pstr /*字符指针指向后缀表达式串的第一个字符 */ while (*ptr!=0) if(*ptr= ) /*当前字符是空格 */ (1) ; /*字符指针指向下一字符 */
18、 continue; else if (isdigit(*ptr) /*当前字符是数字，则将该数字开始的数字串转换为数值 */ tnum= (2) ; while (*ptr =0 ptr+; push( (4) ); else /*当前字符是运算符或其他符号 */ if (*ptr=+|*ptr=-|*ptr=*|*ptr=/) if(!IsEmpty(S) a=Top(s); Pop( /*取运算符的第二个运算数 */ if(!IsEmpty(S) b=Top(s); Pop( /*取运算符的 第一个运算数 */ else return-1; else return -1; switch
19、(*ptr) case+: Push( break; case-: Push( break; case+: Push( break; case/: Push( break; else return -1; ptr+; /*字符指针指向下一字符 */ /*while*/ if (IsEmpty(s) return -1; else (5) =Top(s); Pop( /*取运算结果 */ if (!IsEmpty(s) return -1; return 0; 28 说明 已知某二叉树的非叶子节点都有两个孩子节点，现将该二叉树存储在结构数组 Ht中。节点结构及数组 Ht的定义如下： #defin
20、e MAXLEAFNUM 30 Struct node char ch; char *pstr; int parent; int lchild, rchiid; ; Struct node Ht2 *MAXLEAFNUM; 该二叉树的 n个叶子节点存储在下标为 1 n的 Ht数组元素中。例如，某二叉树如图 8-26所示， 其存储结构如图 8-27所示，其中，与叶子节点 a对应的数组元素下标为 1， a的父节点存储在 Ht5，表示为 Ht1.parent=5。Ht7.parent=0表示 7号节点是树根， Ht7.lchild=3、 Ht7.rchild=6分别表示 7号节点的左孩子是 3号节点
21、、右孩子是 6号节点。 如果用 “0”或 “1”分别标识二叉树的左分支和右分支如图 8-26所示，从根节点开始到叶子节点为止，按所经过分支的次序将相应标识依次排列，可得到一个 0、 1序列，称之为对应叶子节点的编码。例如，图 8-26中 a、 b、 c、 d的 编码分别是 100、 101、 0、 11。 函数 LeafCode(Ht，n)的功能是：求解存储在 Ht中的二叉树中所有叶子节点 (n个 )的编码，叶子节点存储在 Ht1 Htn中，求出的编码存储区由对应的数组元素 pstr域指示。函数 typedef enum Status ERROR， OK Status; Status Leaf
22、Code (Struet node Ht, int n) int pc, pf; int i, start; char tstr31=0); for(i=1; (1) ; i+) start=29; pc=i; pf=Hti.parent; while(Pf!= (2) ) if( (3) . lchiid=pc) tstr-start=0; else tstr-start=1; pc= (4) ; pf=HtPf.parent; Hti.pstr=(char*)malloc(31-start); if(!Hti.pstr)return ERROR; strcpy(Hti. pstr, (5)
23、 ; return OK; 29 说明 已知包含头节点 (不存储元素 )的单链表的元素已经按照非递减方式排序，函数 compress(NODE *head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。 处理过程中，当元素重复出现时，保留元素第一次出现所在的节点。 图8-29(a)、 (b)是经函数 compress( )处理前后的链表结构示例图。链表的节点类型定义如下： typedef struct Node int data; struct Node *next; NODE; C语言函数 void compress(NODE *head) NODE *ptr, *q; ptr= (
24、1) ; /*取得第一个元素节点的指针 */ while( (2) while(q free(q); q=ptr- next; (5) =ptr- next; /*end of while*/ /*end of compress*/ 30 说明 下面流程图的功能是 ：在已知字符串 A中查找特定字符串 B，如果存在，则输出 B串首字符在 A串中的位置，否则输出 -1。设串 A由 n个字符 A(0)、A(1)、 、 A(n-1)组成，串 B由 m个字符 B(0)、 B(1)、 、 B(m-1)组成，其中 nm 0。在串 A中查找串 B的基本算法如下：从串 A的首字符 A(0)开始，取子串A(0)A
25、(1)i(m -1)与串 B比较；若不同，则再取子串 A(1)A(2)A(m) 与串 B比较，以此类推。 例如，字符串 “CABBRFFD”中存在字符子串 “BRF”(输出 3)，不存在字符子串 “RFD”(输出 -1)。 在流程 图中， i用于访问串 A中的字符 (i=0， 1， ， n-1)， j用于访问串 B中的字符 (j=0， 1， ， m-1)。在比较 A(i)A(i+1)A(i+m -1)与B(0)B(1)B(m -1)时，需要对 A(i)与 B(0)、 A(i+1)与 B(1)、 、 A(i+j)与 B(j)、 逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，以此类推。
26、 流程图 本题流程图如图 8-30所示。数据结构与算法练习试卷 1答案与解析 1 【正确答案】 D 【知识模块】 数据结构与算法 2 【正确答案】 B 【知识模块】 数据结构与算法 3 【正确答案】 B 【知识模块】 数据结构与算法 4 【正确答案】 C 【知识模块】 数据结构与算法 5 【正确答案】 B 【知识模块】 数据结构与算法 6 【正确答案】 C 【知识模块】 数据结构与算法 7 【正确答案】 C 【知识模块】 数据结构与算法 8 【正确答案】 A 【知识模块】 数据结构与算法 9 【正确答案】 A 【知识模块】 数据结构与算法 10 【正确答案】 D 【知识模块】 数据结构与算法
27、11 【正确答案】 B 【知识模块】 数据结构与算法 12 【正确答案】 D 【知识模块】 数据结构与算法 13 【正确答案】 C 【知识模块】 数据结构与算法 14 【正确答案】 B 【知识模块】 数据结构与算法 15 【正确答案】 D 【知识模块】 数据结构与算法 16 【正确答案】 D 【知识模块】 数据结构与算法 17 【正确答案】 A 【知识模块】 数据结构与算法 18 【正确答案】 B 【知识模块】 数据结构与算法 19 【正确答案】 B 【知识模块】 数据结构与算法 20 【正确答案】 C 【知识模块】 数据结构与算法 21 【正确答案】 B 【知识模块】 数据结构与算法 22
28、【正确答案】 A 【知识模块】 数据结构与算法 23 【正确答案】 B 【知识模块】 数据结构与算法 24 【正确答案】 D 【知识模块】 数据结构与算法 25 【正确答案】 ptr- next head- next ptr!=endptr，或其他等价形式 ptr preptr 【知识模块】 数据结构与算法 26 【正确答案】 n SIZE，或其等价表示 n*n col+，或 +col，或 col=col+1，或其等价表示 col-=n，或 col=1，或其等价表示 value+1，或其等价表示 【试题解析】 程序中空 (1)处判断 n的合法性， n需为奇数，矩阵规模应不超过SIZE2。所以
29、(1)处应为 n SIZE，或其等价表示。将数值填入方阵的语句为“arowcol=value;”，该语句在循环中，循环条件为 “value =n*n”，所以 (2)处应填入 “n*n”。对于 3阶魔方阵， 1填入第 1行第 2列， 2填入第 3行第 3列， 3填入第 2行第 1列，其余位置按照算法步骤类推。所以 (3)处填入 “col+”或其等价形式， (4)处填入 “col=1”或 “col-=n”。程序中，本次填入的数值为 value的值，下一次要填入的数值为 vahle加 1，因此，空 (5)处应填入 “value+1”。 【知识模块】 数据结构与算法 27 【正确答案】 ptr+，或
30、+ptr，或 ptr=ptr+1，或其等价表示 0，或 tnum=0 *ptr-48，或 *ptr-0，或其等 价表示 ptr=head- next; /*取得第一个元素节点的指针 */ while(ptr while(q free(q); q=ptr- next; ptr=ptr- next; /*end of while*/ /*end of compress*/ 【知识模块】 数据结构与算法 30 【正确答案】 j+1 i+1 0 i -1 【试题解析】 依题意，在已知字符串 A中查找特定字符串 B，基本算法如下：从串 A的首字符 A(0)开始，取子串 A(0)A(1)A(m -1)与串 B比较；若不同，则再取子串 A(1)A(2)A(m) 与串 B比较，以此类推。我们可以采用两重循环来实现。初始时， i与 j都设为 0， i范围为 0至 n-1， j范围为 m-1，比较 A(i+j)与 B(j)是否相等，在循环过程中只 要存在一个 j使得 A(i+j)不等于 B(i)，则退出本次循环， i+1后重新进行遍历。如果最后 i n-m则说明不存在 B字符串。否则，返回 B字符串的位置。 【知识模块】 数据结构与算法
