数 据 结 构 习 题绪论一,单项选择数据结构是一门研究非数值计算的程序设计问题中计算机的 __A①___以及它们之间的__A②__和运算等的学科。
① A）操作对象 B） 计算方法 C） 逻辑存储 D） 数据映象
② A）结构 B）关系 C）运算 D）算法数据结构被形式地定义为（K，R），其中K是__B①___的有限集合，R是K上的 D② 有限集合。
① A）算法 B）数据元素 C）数据操作 D）逻辑结构
② A）操作 B）映象 C）存储 D）关系在数据结构中，从逻辑上可以把数据结构分成__C①___。
① A）动态结构和静态结构 B）紧凑结构和非紧凑结构
C）线性结构和非线性结构 D）内部结构和外部结构线性表的顺序存储结构是一种_ A①_的存储结构，线性表的链式存储结构是一种_②_的存储结构。
A) 随机存取 B) 顺序存取 C) 索引存取 D) 散列存取算法分析的目的是__C①___，算法分析的两个主要方面是__A②___。
① A) 找出数据结构的合理性 B) 研究算法中的输入和输出关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
② A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性计算机算法指的是 C①,它必具备输入、输出和 ②B 等五个特性。
① A) 计算方法 B) 排序方法
C) 解决问题的有限操作序列 D) 调度方法
② A) 可行性、可移植性和可扩充性 B）可行性、确定性和有穷性
C）确定性、有穷性和稳定性 D）易读性、稳定性和安全性计算机执行下面程序段时，语句S的执行次数为__①B__
for (i=1; i<n; i++)
for(j=n;j>=i;j--) S;
① A) n(n+2)/2 B) (n-1)(n+2)/2 C) n(n+1)/2 D) (n-1)(n+2)
线性表的逻辑顺序与存储顺序总是一致的，这种说法_① B _。
① A） 正确 B） 不正确线性表若采用链式存储结构时，要求内存中可用存储单元的地址_①_D。
① A) 必须是连续的 B) 部分地址必须是连续的
C) 一定是不连续的 D) 连续或不连续都可以每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__①B___。
① A) 正确 B) 不正确二,填空题(将正确的答案填在相应的中)
1,数据逻辑结构包括__①线性结构___、__②树型结构___和__③图形结构___三种类型，树形结构和图形结构合称为__④非线性结构___。
2,在线性结构中，第一个结点__①无___前驱结点，其余每个结点有且只有__②一___个前驱结点；最后一个结点__③无__后续结点，其余每个结点有且只有__④一___个后续结点。
树形结构中，树根结点没有__①前驱__结点，其余每个结点有且只有 ②一 个前驱结点；叶子结点没有______③后继____结点，其余每个结点的后续结点可以___④多个__。
图形结构中，每个结点的前驱结点数和后续结点数可以__①多个___。
线性结构中元素之间存在__①1对1___关系，树形结构中元素之间存在__②一对多___关系，图形结构中元素之间存在_③_多对多___关系。
算法的五个重要特性是__①输入__、_②_输出___、__③可行性___、_④确定性____、__⑤有穷性___。
下面程序段的时间复杂度是__①_O（n×n）__。
for (i=0; i<n; i++)
for (j=0; j<m; j++)
A[i][j]=0;
下面程序段的时间复杂度是___①O（n）__。
i=s=0;
while (s<n)
{
i++; /*i=i+1*/
s+=i; /*s=s+i*/
}
下面程序段的时间复杂度是__①_ O（n×n）__。
s=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
s+=B[I][j];
sum=s;
下面程序段的时间复杂度是__①O（n）___。
i=1;
while (i<=n)
i=i*3;
第二章 线性表
说明：顺序存储的线性表称为向量。
一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。
A) 110 B) 108 C) 100 D) 120
线性结构通常采用的两种存储结构是__①A___。
A) 顺序存储结构和链式存储结构 B) 散列方式和索引方式
C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.
A) head==NULL B) head->next==NULL
C) head->next==head D) head!=NULL
带头结点的单链表head为空的判定条件是__①B___。
A) head==NULL B) head->next==NULL
C) head->next==head D) head!=NULL
非空的循环链表head的尾结点（由p所指向）满足__①_C__。
A) p->next==NULL B) p==NULL
C) P->next==head D) p==head
在循环双链表的p所指结点之后插入s所指结点的操作是___①_C_。
A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;
B) p->right=s; p->right->left=s; s->left=p; s->right=p->right;
C) s->left=p; s->right=p->right; p->right=s; p->right->left=s;
D) s->left=p; s->right=p->right; p->right->left=s; p->right=s;
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点,
则执行__①c___。
A) s->next=p->next; p->next=s; B) p->next=s->next; s->next=P;
C) q->next=s; s->next=p; D) p->next=s; s->next=q;
在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行__①b___。
A) s->next=p; p->next=s; B) s->next=p->next; p->next=s;
C) s->next=p->next; p=s; D) p->next=s; s->next=p;
在一个单链表中，若删除p所指结点的后续结点，则执行__①_a__。
A) p->next=p->next->next; B) p=p->next; p->next=p->next->next;
C) p->next=p->next; D) p=p->next->next;
10,假设双链表结点的类型如下：
typedef struct linknode
{
int data,/*数据域*/
struct linknode * llink; /*llink是指向前驱结点的指针域*/
struct linknode * rlink; /*rlink是指向后续结点的指针域*/
} bnode
要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，
其算法是__①_c__。
q->rlink=p; q->llink=p->llink; p->llink=q; p->llink->rlink=q;
p->llink=q; q->llink=p; p->llink->rlink=q; q->llink=p->llink;
q->llink=p->llink; q->rlink=p; p->llink->rlink=q; p->llink=q;
以上都不对,
12,从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较
__①_d__个结点。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__①_b__。
A) O(1) B) O(n) C) O(n2) D) O(nlog2n)
给定有n个元素的向量，建立一个有序单链表的时间频度是__①_d__。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
二.填空题(将正确的答案填在相应的空中)
单链表是_线性表____的链接存储表示。
向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动__n-i___个元素。
可以使用_二叉链表____表示树形结构。
在双链表中，每个结点有两个指针域，一个指向__直接前驱___，另一个指向_直接后继____。
在一个单链表中的p所指结点之前插入一个s所指结点时，可执行哪些操作_____。
在一个单链表中删除p所指结点时，应执行的操作_____。
带有一个头结点的单链表head为空的条件是 head->next==NULL_____。
在一个单链表中p所指结点之后插入一个s所指结点时，应执行 s->next=_p->next______和 p->next=_s________的操作。
9,非空的循环链表head的尾结点（由p所指向），满足条件__p->next=head___。
10,对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__o(1)___； 在给定值为x的结点后插入一个新结点的时间复杂度是_o(n)____。
栈和队列个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是__c___。
A) edcba B) dceba C) dceab D) abcde
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为__c___。
A) i B) n-i C) n-i+1 D) 不确定
判定一个栈ST（最多元素为m0）为空的条件是_b____。
A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0
判定一个栈ST（最多元素为m0）为栈满的条件是_d____。
A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0
栈的特点是__①b___，队列的特点是__②_a__。
A) 先进先出 B) 先进后出在以下的叙述中，正确的是__①_c__。
A) 线性表的线性存储结构优于链表存储结构 B) 栈的操作方式是先进先出
C) 二维数组是其数据元素为线性表的线性表 D) 队列的操作方式是先进后出一个队列的入队序列是1，2，3，4，则队列的输出序列是__b___。
A) 4,3,2,1 B) 1,2,3,4 C) 1,4,3,2 D) 3,2,4,1
判定一个循环队列QU（最多元素为m0）为空的条件是_a____。
A) QU->front==QU->rear B) QU->front!=QU->rear
C) QU->front==(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0
判定一个循环队列QU（最多元素为m0）为满队列的条件是_d____。
A) QU->front==QU->rear B) QU->front!=QU->rear
C) QU->front==(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0
循环队列用数组A[m]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是__a___。
A) (rear-front+m)%m B) rear-front+1 C) rear-front-1 D) rear-front
栈和队列的共同点是__c___。
A) 都是先进后出 B) 都是先进先出 C) 只允许在端点处插入和删除 D) 没有共同点
向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_c____。
A) HS->next=s; B) s->next=HS->next; HS->next=s;
C) s->next=HS; HS==s; D) s->next=HS; HS=HS->next;
从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__d___。
A) x=HS; HS=HS->next; B) x=HS->data;
C) HS=HS->next; x=HS->data; D) x=HS->data; HS=HS->next;
在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时__b___。
A) f->next=s; f=s; B) r->next=s; r=s;
C) s->next=r; r=s; D) s->next=f; f=s;
17,在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时__c___。
A) r=f->next; B) r=r->next; C) f=f->next; D) f=r->next;
二,填空题(将正确的答案填在相应的空中)
向量、栈和队列都是_线性____结构，可以在向量的__端点___位置插入和删除元素；对于栈只能在 _栈顶____插入和删除元素；对于队列只能在_队尾____插入元素和__队头___删除元素。
向一个长度为n的向量的第i个元素之前插入一个元素时，需向后移动_n-i+1____个元素。
向栈中压入元素的操作是_置入数据，栈顶指针加1____。
对栈进行退栈时的操作是_栈顶指针减1，取出数据____。
在一个循环队列中，队尾指针指向队尾元素的_直接后继____。
从循环队列中删除一个元素时，其操作是__取出队头指针所指数据元素，队头指针加1___。
在具有n个单元的循环队列中，队满时共有_n-1____个元素。
一个栈的输入序列是12345，则栈的输出序列43512是_错误的____。
一个栈的输入序列是12345，则栈的输出序列12345是_正确的____。
在栈顶指针为HS的链栈中，判定栈空的条件是_HS==NULL____。
在栈顶指针为HS的链栈中，计算该链栈中结点个数的函数是 _遍历函数____。
串一,单项选择题空串与空格串是相同的，这种说法_b___。
A) 正确 B) 不正确串是一种特殊的线性表，其特殊性体现在__b___。
A) 可以顺序存储 B) 数据元素是一个字符
C) 可以链接存储 D) 数据元素可以是多个字符设有两个串p和q，求q在p中首次出现的位置的运算称作__b___。
A) 连接 B) 模式匹配 C) 求子串 D) 求串长设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是_d____。
A) BCDEF B) BCDEFG C) BDPQRST D) BCDEFEF
二,填空题串的两种最基本的存储方式是_顺序和链式____。
两个串的长度相等的充分必要条件是_有效字符相同____。
空串是_“”____其长度等于_0____。
空格串是_由空格组成的字符串____，其长度等于__空格的个数___。
设s=“I AM A TEACHER”其长度是 14_____。
设s1=’GOOD’,s2=’ ’,s3=’BYE!’,则s1、s2和s3连接后的结果是_GOOD BYE!____。
数组和广义表一,单项填空题(其中A[i...j]表示下标i到j)
常对数组进行的两种基本操作是__C___。
A) 建立与删除 B) 索引与修改 C) 查找和修改 D) 查找与索引二维数组M的每个成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要__①_D__个字节；M的第8列和第5行共占__②_A__个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的__③B___元素的起始地址一致。
① A) 90 B) 180 C) 240 D) 540
② A) 102 B) 114 C) 54 D) 60
③ A) M[8][5] B) M[3][10] C) M[5][8] D) M[0][9]
二维数组M的每个元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素__B___的起始地址相同。
A） M[2][4] B) M[3][4] C) M[3][5] D) M{4}[4]
数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放数组至少需要的单元数是_C____。
A) 80 B) 100 C) 240 D) 270
数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为___C__。
A) SA+141 B) SA+144 C) SA+222 D) SA+255
数组A中，每个元素A的长度为3个字节，行下标从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为_B____。
A) SA+141 B) SA+144 C) SA+222 D) SA+255
稀疏矩阵一般的压缩存储方法有两种，即_C____。
A) 二维数组和三维数组 B） 三元组和散列
C） 三元组和十字链表 D） 散列和十字链表若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点__A___ 。
A） 正确 B） 错误设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一元素ai,j(i≥j)，在一组数组B中下标k的值是_B____。
A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j
a1,1
a2,1 a2,2
A=,..
an,1 an,2,.,an,n
10,广义表（（a）,a）的表头是__C_①__，表尾是__②_C__。
A) a B) () C) (a) D) ((a))
广义表（（a））的表头是__①B___，表尾是__②_C__。
A) a B) (a) C) () D) ((a))
广义表((a,b),c,d)的表头是__①_C__，表尾是__②__D_。
A) a B) b C) (a,b) D) (c,d)
广义表(a,b,c,d)表头是__①_A__，表尾是__②_D__。
A) a B) b C) (a,b) D) (b,c,d)
广义表（（a,b,c,d））的表头是__①_C__，表尾是__②_B__。
A) a B) () C) (a,b,c,d) D) ((a,b,c,d))
一个广义表的表头总是一个广义表，这个断言是_B____。
A) 正确 B） 不正确一个广义表的表尾总是一个广义表，这个断言是__A___。
A）正确 B） 不正确二．填空题
1,已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个的存储地址是LOC（A[0][0]），则A[i][j]的地址是_____。
2,二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是_____。
二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是_____。
有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是_____。
设n行n列的下三角矩阵A已压缩到一维数组S[1..n * (n+1)/2]中，若按行序为主存储，则A[i][j]对应的S中的存储位置是_____。
一个稀疏矩阵如图所示，则对应的三元组表示为_____。
0 0 2 0
3 0 0 0
0 0 -1 5
0 0 0 0
7.广义表（（（a）））的表头是_（（a））____，表尾是_()____。
8.广义表（（a）,((b),c)，（（（d））））的表头是_（a）____，表尾是(((b),c)，（（（d）））)_____。
9.广义表（（a）,((b),c),(((d)))）的长度是__3___，深度是_3____。
10.广义表（a,(a,b),d,e,((i,j),k)）的长度是_5____，深度是_2____。
11.设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[]是函数的符号，给出下列广义表的运算结果：
HEAD[(a,b,c)]的结果是_a____。
TAIL[(a,b,c)]的结果是__(b,c)___。
HEAD[((a),(b))]的结果是_(a)____。
TAIL[（（a）,(b)）]的结果是_((b))____。
HEAD[TAIL[(a,b,c)]的结果是__b___。
TAIL[HEAD((a,b),(c,d))]的结果是_(b)____。
HEAD[HEAD[(（a,b）,(c,d))]]的结果是_a____。
TAIL[TAIL[(a,(c,d))]]的结果是_()____。
树形结构一．单项选择题
1,如图所示的4棵二叉树中，__c___不是完全二叉树。
（A） （B） （C） （D）
2．如图所示的4棵二叉树，__b___是平衡二叉树。
（A） （B） （C） （D）
在线索化二叉树中，t所指结点没有左子树的充要条件是_b____。
A） t->left=NULL B) t->ltag=1
C) t->ltag=1且t->left=NULL D) 以上都有不对二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法_b____。
A） 正确 B） 错误二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__a___。
A） 正确 B） 错误由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_b____。
A） 正确 B） 错误设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_b____。
A） 2h B) 2h-1 C) 2h+1 D) h+1
如图所示二叉树的中序遍历序列是__b___。
A) abcdgef B) dfebage C) dbaefcg D) defbagc
9.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，
它的前序遍历序列是__d____。
A) acbed B) decab C) deabc D) cedba
如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的_a____。
A) 前序 B） 中序 C） 后序 D） 层次序如果T2是由有序树T转换而来的二叉结，那么T中结点的后序就是T2中结点的_b____。
A) 前序 B） 中序 C） 后序 D） 层次序某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_d____。
A） bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca
二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__b___。
A) 正确 B） 不正确按照二叉树的定义，具有3个结点的二叉树有_c____种。
A） 3 B） 4 C） 5 D） 6
一棵二叉树如图所示，其中遍历的序列为_b____。
A） abdgcefh B) dgbaechf C) gdbehfca D) abcdefgh
树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论_a____是正确的。
树的先根遍历序列与其对应的二叉树的先序遍历序列相同树的后根遍历序列与其对应的二叉树的后序遍历序列相同树的先根遍历序列与其对应的二叉树的中序遍历序列相同以上说法都不对深度为5的二叉树至多有_c____个结点。
A） 16 B） 32 C） 31 D） 10
在一非空二叉树的中序遍历序列中，根结点的右边_a____。
A） 只有右子树上的所有结点 B） 只有右子树上的部分结点
C） 只有左子树上的部分结点 D） 只有左子树上的所有对点树最适合用来表示__c___。
A） 有序的数据元素 B） 无序的数据元素
C） 元素之间具有分支层次关系的数据 D）元素之间无联系的数据任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__a___。
A） 不发生改变 B） 发生改变 C） 不能确定 D） 以上都有不对实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_d__存储结构。
A） 二叉链表 B） 广义表存储结构 C） 三叉链表 D） 顺序存储结构对一个满二叉树，m个树叶，n个结点，深度为h，则___d__。
A） n=h+m B) h+m=2n C) m=h-1 D) n=2h-1
如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为_c____。
A) uwvts B) vwuts C) wuvts D) wutsv
t2
如图所示的t2是由有序树t1转换而来的二叉树，那么树t1有_c____个叶结点。
A) 4 B) 5 C) 6 D) 7
设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__c___。
A) n在m的右方 B） n是m的祖先
C）n 在m的左方 D） n是 m的子孙线索二叉树是一种__c___结构。
A） 逻辑 B） 逻辑与存储 C） 物理 D） 线性二．填空题（将正确答案填在相应的空中）
1．一棵树如图所示，回答下面的问题：
棵树的根结点是_k1____。
这棵树的叶结点是__k2,k5,k4,k7___。
结点k3的度是_2____。
这棵树的度为___3__。
这棵树的深度是__4___。
结点k3的子女是__k5,k6,k7___。
结点k3的父结点是__k1___。
4,一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链接表示形式为_____。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
t:
深度为k的完全二叉树至少有_____个结点。至多有_____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_____。
在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0==__n2+1___。
一棵二叉树的第i(i≥1)层最多有_____个结点；一棵有n(n>0)个结点的满二叉树共有_____个叶子和_____个非终端结点。
结点最少的树为_空____树，结点最少的二叉树为_空____树。
现有按中序遍历二叉树的结果为abc，问有__5___种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_____。
根据二叉树的定义，具有三个结点的二叉树有_5____种不同的形态，它们分别是_____。
由如图所示的二叉树,回答以下问题:
其中序遍历序列为__dgbaechif___。
其前序遍历序列为__ abdgcefhi ___。
其后序遍历序列为__ gdbeihfca ___。
该二叉树的中序线索二叉树为_____。
该二叉树的后序线索二叉树为_____。
该二叉树对应的森林是_____。
已知一棵树如右图所示，其孩子兄弟表示为_____。
13．以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为_____，其带权路径长度为_____。
图一．单项选择题在一个图中，所有顶点的度数之和等于所有边数的_c____倍。
A）1/2 B) 1 C) 2 D) 4
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__b___倍。
A) 1/2 B) 1 C) 2 D) 4
一个有n个顶点的无向图最多有__c___条边。
A) n B) n(n-1) C) n(n-1)/2 D) 2n
具有4个顶点的无向完全图有_a____条边。
A) 6 B) 12 C) 16 D) 20
具有6个顶点的无向图至少应有_a____条边才能确保是一个连通图。
A) 5 B) 6 C) 7 D) 8
在一个具有n个顶点的无向图中，要连通全部顶点至少需要__c___条边。
A) n B) n+1 C) n-1 D) n/2
对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_d____。
A) n B) (n-1)2 C) n-1 D) n2
对于一个具有n个顶点和e条边的无向图，若采用邻接表示，则表头向量的大小为__①_a__，所有邻接表中的结点总数是__②c___。
① A) n B) n+1 C) n-1 D) n+e
② A) e/2 B) e C) 2e D) n+e
已知一个图如下所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为
__①d___；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②b_ _。
① A) a,b,c,d,e,f B) a,c,f,e,b,d
C) a,e,b,c,f,d D) a,e,d,f,c,b
② A) a,b,c,d,e,f B) a,b,c,e,f,d
C) a,e,b,c,f,d D) a,c,f,d,e,b
已知一有向图的邻接表存储结构如图所示。
根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是_c____。
A) v1,v2,v3,v5,v4 B) v1,v2,v3,v4,v5 C) v1,v3,v4,v5,v2 D) v1,v4,v3,v5,v2
根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_b____。
A) v1,v2,v3,v4,v5 B) v1,v3,v2,v4,v5 C) v1,v2,v3,v5,v4 D) v1,v4,v3,v5,v2
采用邻接表存储的图的深度优先遍历算法类似于二叉树的_a____。
A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历采用邻接表存储的图的宽度优先遍历算法类似于二叉树的d_____。
A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用__d___。
A） 求关键路径的方法 B） 求最短路径的Dijkstra方法
C） 宽度优先遍历算法 D） 深度优先遍历算法二．填空题（将正确的答案填在相应的空中）
N个顶点的连通图至少_N-1____条边。
在无权图G的邻接矩阵A中，若（vi,vj）或<vi,vj>属于图G的边集合，则对应元素A[i][j]等于_1____，否则等于_0____。
在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_1____。
已知图G的邻接表如图1所示，其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4____，其从顶点v1出发的宽度优先搜索序列为___v1v2v5v4v3v6__。
已知一个图的邻接矩阵表示，计算第I个结点的入度的方法是_____。
已知一个图的邻接矩阵表示，删除所有从第I个结点出发的边的方法是_____。
查找一．单项选择题顺序查找法适合于存储结构为_b____的线性表。
A） 散列存储 B） 顺序存储或链接存储
C） 压缩存储 D） 索引存储对线性表进行二分查找时，要求线性表必须__b___。
A） 以顺序方式存储 B） 以顺序方式存储，且结点关键字有序排序
C） 以链接方式存储 D） 以链接方式存储，且结点关键字有序排序采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_c____。
A） n B) n/2 C) (n+1)/2 D) (n-1)/2
采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为__c___。
A) O(n2) B) O(nlog2n) C) O(n) D) O(log2n)
二分查找和二叉排序树的时间性能__b___。
A) 相同 B） 不相同有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，___c__次比较后查找成功。
A） 1 B） 2 C） 4 D） 8
设哈希表长m=14，哈希函数H(key)=key % 11。表中已有4个结点：
addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7
其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是__d___。
A） 8 B） 3 C） 5 D） 9
8．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为__b___。
A） 35/12 B） 37/12 C） 39/12 D） 43/12
分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分__b___个结点最佳。
A） 10 B） 25 C） 6 D） 625
如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_d____查找方法。
A） 分块 B） 顺序 C） 二分 D） 散列
二．填空题顺序查找法的平均查找长度为_____；二分查找法的平均查找长度为_____；分块查找法（以顺序查找确定块）的平均查找长度为_____；分块查找法（以二分查找确定块）的平均查找长度为_____；哈希表查找法采用链接法处理冲突时的平均查找长度为_____。
在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____。
二分查找的存储结构仅限于_____，且是_____。
在分块查找方法中，首先查找_____，然后再查找相应的_____。
长度为255的表，采用分块查找法，每块的最佳长度是_____。
在散列函数H(key)=key % p中，p应取_____。
假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为_10____，则比较二次查找成功的结点数为_5,15____，则比较三次查找成功的结点数为_2,7_12,18___，则比较四次查找成功的结点数为_1,3_,6,8,,11,13,16,19___，则比较五次查找成功的结点数为 _4,9,14,17,20____，平均查找长度为_3.7____。
对于长度为n的线性表，若进行顺序查找，则时间复杂度为__o(n)___；若采用二分法查找，则时间复杂度为_o(logn)____。
在散列存储中，装填因子α的值越小，则_发生冲突的机会越小____。
内排序一．选择填空题在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_d____。
A） 希尔排序 B） 起泡排序 C） 插入排序 D） 选择排序设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_d____排序法。
A） 起泡排序 B） 快速排序 C） 堆排序 D） 基数排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是_a____。
A） 插入排序 B） 选择排序 C） 快速排序 D） 归并排序一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_b____。
A） 79，46，56，38，40，80 B） 84，79，56，38，40，46
C） 84，79，56，40，38 D） 84，56，79，40，46，38
一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为__c___。
A） 38，40，46，56，79，84 B） 40，38，46，79，56，84
C） 40，38，46，56，79，84 D） 40，38，46，84，56，79
一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为__a___。
A）16，25，35，48，23，40，79，82，36，72
B）16，25，35，48，79，82，23，36，40，72
C）16，25，48，35，79，82，23，36，40，72
D）16，25，35，48，79，23，36，40，72，82
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__c___。
A） 希尔排序 B） 起泡排序 C） 插入排序 D） 选择排序排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为__d___。
A） 希尔排序 B） 归并排序 C） 插入排序 D） 选择排序用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
（1）25，84，21，47，15，27，68，35，20
（2）20，15，21，25，47，27，68，35，84
（3）15，20，21，25，35，27，47，68，84
（4）15，20，21，25，27，35，47，68，84
则所采用的排序方法是__c___。
A） 希尔排序 B） 归并排序 C） 快速排序 D） 选择排序下述几种排序方法中，平均时间复杂度最小的是_a____。
A） 快速排序 B） 归并排序 C） 插入排序 D） 选择排序下述几种排序方法中，要求内存量最大的是__b___。
A） 快速排序 B） 归并排序 C） 插入排序 D） 选择排序快速排序方法在__c___情况下最不利于发挥其长处。
A） 要排序的数据量太大 B）要排序的数据中含有多个相同的值
C） 要排序的数据已基本有序 D） 要排序的数据个数为奇数
二．填空题在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_3____次。
在堆排序，快速排序和归并排序中，若只从存储窨考虑，则应首先选取_堆排序____方法，其次选取_快速排序____方法，最后选取归并排序_方法；若只从排序结果的稳定性考虑，则应选取_归并排序____方法；若只从平均情况下排序最快考虑，则应选取_快速排序____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取__堆排序____方法。
在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有__希尔排序、快速排序、堆排序___。
在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是_基数排序____，需要内存容量最多的是_归并排序____。
在堆排序和快速排序中，若原始记录接近正序或反序，则选用_堆排序____，若原始记录无序，则最好选用__快速排序___。
在插入和选择排序中，若初始数据基本正序，则选用_插入排序____；若初始数据基本反序，则选用__选择排序___。
对n个元素的序列进行起泡排序时，最少的比较次数是_n-1____。
① A）操作对象 B） 计算方法 C） 逻辑存储 D） 数据映象
② A）结构 B）关系 C）运算 D）算法数据结构被形式地定义为（K，R），其中K是__B①___的有限集合，R是K上的 D② 有限集合。
① A）算法 B）数据元素 C）数据操作 D）逻辑结构
② A）操作 B）映象 C）存储 D）关系在数据结构中，从逻辑上可以把数据结构分成__C①___。
① A）动态结构和静态结构 B）紧凑结构和非紧凑结构
C）线性结构和非线性结构 D）内部结构和外部结构线性表的顺序存储结构是一种_ A①_的存储结构，线性表的链式存储结构是一种_②_的存储结构。
A) 随机存取 B) 顺序存取 C) 索引存取 D) 散列存取算法分析的目的是__C①___，算法分析的两个主要方面是__A②___。
① A) 找出数据结构的合理性 B) 研究算法中的输入和输出关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
② A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性计算机算法指的是 C①,它必具备输入、输出和 ②B 等五个特性。
① A) 计算方法 B) 排序方法
C) 解决问题的有限操作序列 D) 调度方法
② A) 可行性、可移植性和可扩充性 B）可行性、确定性和有穷性
C）确定性、有穷性和稳定性 D）易读性、稳定性和安全性计算机执行下面程序段时，语句S的执行次数为__①B__
for (i=1; i<n; i++)
for(j=n;j>=i;j--) S;
① A) n(n+2)/2 B) (n-1)(n+2)/2 C) n(n+1)/2 D) (n-1)(n+2)
线性表的逻辑顺序与存储顺序总是一致的，这种说法_① B _。
① A） 正确 B） 不正确线性表若采用链式存储结构时，要求内存中可用存储单元的地址_①_D。
① A) 必须是连续的 B) 部分地址必须是连续的
C) 一定是不连续的 D) 连续或不连续都可以每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__①B___。
① A) 正确 B) 不正确二,填空题(将正确的答案填在相应的中)
1,数据逻辑结构包括__①线性结构___、__②树型结构___和__③图形结构___三种类型，树形结构和图形结构合称为__④非线性结构___。
2,在线性结构中，第一个结点__①无___前驱结点，其余每个结点有且只有__②一___个前驱结点；最后一个结点__③无__后续结点，其余每个结点有且只有__④一___个后续结点。
树形结构中，树根结点没有__①前驱__结点，其余每个结点有且只有 ②一 个前驱结点；叶子结点没有______③后继____结点，其余每个结点的后续结点可以___④多个__。
图形结构中，每个结点的前驱结点数和后续结点数可以__①多个___。
线性结构中元素之间存在__①1对1___关系，树形结构中元素之间存在__②一对多___关系，图形结构中元素之间存在_③_多对多___关系。
算法的五个重要特性是__①输入__、_②_输出___、__③可行性___、_④确定性____、__⑤有穷性___。
下面程序段的时间复杂度是__①_O（n×n）__。
for (i=0; i<n; i++)
for (j=0; j<m; j++)
A[i][j]=0;
下面程序段的时间复杂度是___①O（n）__。
i=s=0;
while (s<n)
{
i++; /*i=i+1*/
s+=i; /*s=s+i*/
}
下面程序段的时间复杂度是__①_ O（n×n）__。
s=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++)
s+=B[I][j];
sum=s;
下面程序段的时间复杂度是__①O（n）___。
i=1;
while (i<=n)
i=i*3;
第二章 线性表
说明：顺序存储的线性表称为向量。
一,单项选择题一个向量第一个元素的地址是100，每个元素的长度为2，则第5个元素的地址是__①_B__。
A) 110 B) 108 C) 100 D) 120
线性结构通常采用的两种存储结构是__①A___。
A) 顺序存储结构和链式存储结构 B) 散列方式和索引方式
C) 链表存储结构和数组 D) 线性存储结构和非线性存储结构不带头结点的单链表head为空的判定条件是__①__A_.
A) head==NULL B) head->next==NULL
C) head->next==head D) head!=NULL
带头结点的单链表head为空的判定条件是__①B___。
A) head==NULL B) head->next==NULL
C) head->next==head D) head!=NULL
非空的循环链表head的尾结点（由p所指向）满足__①_C__。
A) p->next==NULL B) p==NULL
C) P->next==head D) p==head
在循环双链表的p所指结点之后插入s所指结点的操作是___①_C_。
A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;
B) p->right=s; p->right->left=s; s->left=p; s->right=p->right;
C) s->left=p; s->right=p->right; p->right=s; p->right->left=s;
D) s->left=p; s->right=p->right; p->right->left=s; p->right=s;
在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点,
则执行__①c___。
A) s->next=p->next; p->next=s; B) p->next=s->next; s->next=P;
C) q->next=s; s->next=p; D) p->next=s; s->next=q;
在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行__①b___。
A) s->next=p; p->next=s; B) s->next=p->next; p->next=s;
C) s->next=p->next; p=s; D) p->next=s; s->next=p;
在一个单链表中，若删除p所指结点的后续结点，则执行__①_a__。
A) p->next=p->next->next; B) p=p->next; p->next=p->next->next;
C) p->next=p->next; D) p=p->next->next;
10,假设双链表结点的类型如下：
typedef struct linknode
{
int data,/*数据域*/
struct linknode * llink; /*llink是指向前驱结点的指针域*/
struct linknode * rlink; /*rlink是指向后续结点的指针域*/
} bnode
要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，
其算法是__①_c__。
q->rlink=p; q->llink=p->llink; p->llink=q; p->llink->rlink=q;
p->llink=q; q->llink=p; p->llink->rlink=q; q->llink=p->llink;
q->llink=p->llink; q->rlink=p; p->llink->rlink=q; p->llink=q;
以上都不对,
12,从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较
__①_d__个结点。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__①_b__。
A) O(1) B) O(n) C) O(n2) D) O(nlog2n)
给定有n个元素的向量，建立一个有序单链表的时间频度是__①_d__。
A) n B) n/2 C) (n-1)/2 D) (n+1)/2
二.填空题(将正确的答案填在相应的空中)
单链表是_线性表____的链接存储表示。
向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动__n-i___个元素。
可以使用_二叉链表____表示树形结构。
在双链表中，每个结点有两个指针域，一个指向__直接前驱___，另一个指向_直接后继____。
在一个单链表中的p所指结点之前插入一个s所指结点时，可执行哪些操作_____。
在一个单链表中删除p所指结点时，应执行的操作_____。
带有一个头结点的单链表head为空的条件是 head->next==NULL_____。
在一个单链表中p所指结点之后插入一个s所指结点时，应执行 s->next=_p->next______和 p->next=_s________的操作。
9,非空的循环链表head的尾结点（由p所指向），满足条件__p->next=head___。
10,对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__o(1)___； 在给定值为x的结点后插入一个新结点的时间复杂度是_o(n)____。
栈和队列个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是__c___。
A) edcba B) dceba C) dceab D) abcde
若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…,pn,若p1=n，则pi为__c___。
A) i B) n-i C) n-i+1 D) 不确定
判定一个栈ST（最多元素为m0）为空的条件是_b____。
A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0
判定一个栈ST（最多元素为m0）为栈满的条件是_d____。
A) ST->top!=0 B) ST->top==0 C) ST->top!=m0 D) ST->top==m0
栈的特点是__①b___，队列的特点是__②_a__。
A) 先进先出 B) 先进后出在以下的叙述中，正确的是__①_c__。
A) 线性表的线性存储结构优于链表存储结构 B) 栈的操作方式是先进先出
C) 二维数组是其数据元素为线性表的线性表 D) 队列的操作方式是先进后出一个队列的入队序列是1，2，3，4，则队列的输出序列是__b___。
A) 4,3,2,1 B) 1,2,3,4 C) 1,4,3,2 D) 3,2,4,1
判定一个循环队列QU（最多元素为m0）为空的条件是_a____。
A) QU->front==QU->rear B) QU->front!=QU->rear
C) QU->front==(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0
判定一个循环队列QU（最多元素为m0）为满队列的条件是_d____。
A) QU->front==QU->rear B) QU->front!=QU->rear
C) QU->front==(QU->rear+1)%m0 D) QU->front!=(QU->rear+1)%m0
循环队列用数组A[m]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是__a___。
A) (rear-front+m)%m B) rear-front+1 C) rear-front-1 D) rear-front
栈和队列的共同点是__c___。
A) 都是先进后出 B) 都是先进先出 C) 只允许在端点处插入和删除 D) 没有共同点
向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_c____。
A) HS->next=s; B) s->next=HS->next; HS->next=s;
C) s->next=HS; HS==s; D) s->next=HS; HS=HS->next;
从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__d___。
A) x=HS; HS=HS->next; B) x=HS->data;
C) HS=HS->next; x=HS->data; D) x=HS->data; HS=HS->next;
在一个链队中，假设f和r分别为队首和队尾指针，则插入s所指结点的运算时__b___。
A) f->next=s; f=s; B) r->next=s; r=s;
C) s->next=r; r=s; D) s->next=f; f=s;
17,在一个链队中，假设f和r分别为队首和队尾指针，则删除一个结点的运算时__c___。
A) r=f->next; B) r=r->next; C) f=f->next; D) f=r->next;
二,填空题(将正确的答案填在相应的空中)
向量、栈和队列都是_线性____结构，可以在向量的__端点___位置插入和删除元素；对于栈只能在 _栈顶____插入和删除元素；对于队列只能在_队尾____插入元素和__队头___删除元素。
向一个长度为n的向量的第i个元素之前插入一个元素时，需向后移动_n-i+1____个元素。
向栈中压入元素的操作是_置入数据，栈顶指针加1____。
对栈进行退栈时的操作是_栈顶指针减1，取出数据____。
在一个循环队列中，队尾指针指向队尾元素的_直接后继____。
从循环队列中删除一个元素时，其操作是__取出队头指针所指数据元素，队头指针加1___。
在具有n个单元的循环队列中，队满时共有_n-1____个元素。
一个栈的输入序列是12345，则栈的输出序列43512是_错误的____。
一个栈的输入序列是12345，则栈的输出序列12345是_正确的____。
在栈顶指针为HS的链栈中，判定栈空的条件是_HS==NULL____。
在栈顶指针为HS的链栈中，计算该链栈中结点个数的函数是 _遍历函数____。
串一,单项选择题空串与空格串是相同的，这种说法_b___。
A) 正确 B) 不正确串是一种特殊的线性表，其特殊性体现在__b___。
A) 可以顺序存储 B) 数据元素是一个字符
C) 可以链接存储 D) 数据元素可以是多个字符设有两个串p和q，求q在p中首次出现的位置的运算称作__b___。
A) 连接 B) 模式匹配 C) 求子串 D) 求串长设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是_d____。
A) BCDEF B) BCDEFG C) BDPQRST D) BCDEFEF
二,填空题串的两种最基本的存储方式是_顺序和链式____。
两个串的长度相等的充分必要条件是_有效字符相同____。
空串是_“”____其长度等于_0____。
空格串是_由空格组成的字符串____，其长度等于__空格的个数___。
设s=“I AM A TEACHER”其长度是 14_____。
设s1=’GOOD’,s2=’ ’,s3=’BYE!’,则s1、s2和s3连接后的结果是_GOOD BYE!____。
数组和广义表一,单项填空题(其中A[i...j]表示下标i到j)
常对数组进行的两种基本操作是__C___。
A) 建立与删除 B) 索引与修改 C) 查找和修改 D) 查找与索引二维数组M的每个成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要__①_D__个字节；M的第8列和第5行共占__②_A__个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的__③B___元素的起始地址一致。
① A) 90 B) 180 C) 240 D) 540
② A) 102 B) 114 C) 54 D) 60
③ A) M[8][5] B) M[3][10] C) M[5][8] D) M[0][9]
二维数组M的每个元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素__B___的起始地址相同。
A） M[2][4] B) M[3][4] C) M[3][5] D) M{4}[4]
数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放数组至少需要的单元数是_C____。
A) 80 B) 100 C) 240 D) 270
数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为___C__。
A) SA+141 B) SA+144 C) SA+222 D) SA+255
数组A中，每个元素A的长度为3个字节，行下标从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为_B____。
A) SA+141 B) SA+144 C) SA+222 D) SA+255
稀疏矩阵一般的压缩存储方法有两种，即_C____。
A) 二维数组和三维数组 B） 三元组和散列
C） 三元组和十字链表 D） 散列和十字链表若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点__A___ 。
A） 正确 B） 错误设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B[1..n(n-1)/2]中，对下三角部分中任一元素ai,j(i≥j)，在一组数组B中下标k的值是_B____。
A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j
a1,1
a2,1 a2,2
A=,..
an,1 an,2,.,an,n
10,广义表（（a）,a）的表头是__C_①__，表尾是__②_C__。
A) a B) () C) (a) D) ((a))
广义表（（a））的表头是__①B___，表尾是__②_C__。
A) a B) (a) C) () D) ((a))
广义表((a,b),c,d)的表头是__①_C__，表尾是__②__D_。
A) a B) b C) (a,b) D) (c,d)
广义表(a,b,c,d)表头是__①_A__，表尾是__②_D__。
A) a B) b C) (a,b) D) (b,c,d)
广义表（（a,b,c,d））的表头是__①_C__，表尾是__②_B__。
A) a B) () C) (a,b,c,d) D) ((a,b,c,d))
一个广义表的表头总是一个广义表，这个断言是_B____。
A) 正确 B） 不正确一个广义表的表尾总是一个广义表，这个断言是__A___。
A）正确 B） 不正确二．填空题
1,已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个的存储地址是LOC（A[0][0]），则A[i][j]的地址是_____。
2,二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是_____。
二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是_____。
有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[0][0]=1），则A[8][5]的地址是_____。
设n行n列的下三角矩阵A已压缩到一维数组S[1..n * (n+1)/2]中，若按行序为主存储，则A[i][j]对应的S中的存储位置是_____。
一个稀疏矩阵如图所示，则对应的三元组表示为_____。
0 0 2 0
3 0 0 0
0 0 -1 5
0 0 0 0
7.广义表（（（a）））的表头是_（（a））____，表尾是_()____。
8.广义表（（a）,((b),c)，（（（d））））的表头是_（a）____，表尾是(((b),c)，（（（d）））)_____。
9.广义表（（a）,((b),c),(((d)))）的长度是__3___，深度是_3____。
10.广义表（a,(a,b),d,e,((i,j),k)）的长度是_5____，深度是_2____。
11.设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[]是函数的符号，给出下列广义表的运算结果：
HEAD[(a,b,c)]的结果是_a____。
TAIL[(a,b,c)]的结果是__(b,c)___。
HEAD[((a),(b))]的结果是_(a)____。
TAIL[（（a）,(b)）]的结果是_((b))____。
HEAD[TAIL[(a,b,c)]的结果是__b___。
TAIL[HEAD((a,b),(c,d))]的结果是_(b)____。
HEAD[HEAD[(（a,b）,(c,d))]]的结果是_a____。
TAIL[TAIL[(a,(c,d))]]的结果是_()____。
树形结构一．单项选择题
1,如图所示的4棵二叉树中，__c___不是完全二叉树。
（A） （B） （C） （D）
2．如图所示的4棵二叉树，__b___是平衡二叉树。
（A） （B） （C） （D）
在线索化二叉树中，t所指结点没有左子树的充要条件是_b____。
A） t->left=NULL B) t->ltag=1
C) t->ltag=1且t->left=NULL D) 以上都有不对二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法_b____。
A） 正确 B） 错误二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法__a___。
A） 正确 B） 错误由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法_b____。
A） 正确 B） 错误设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_b____。
A） 2h B) 2h-1 C) 2h+1 D) h+1
如图所示二叉树的中序遍历序列是__b___。
A) abcdgef B) dfebage C) dbaefcg D) defbagc
9.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，
它的前序遍历序列是__d____。
A) acbed B) decab C) deabc D) cedba
如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的_a____。
A) 前序 B） 中序 C） 后序 D） 层次序如果T2是由有序树T转换而来的二叉结，那么T中结点的后序就是T2中结点的_b____。
A) 前序 B） 中序 C） 后序 D） 层次序某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_d____。
A） bdgcefha B) gdbecfha C) bdgaechf D) gdbehfca
二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法__b___。
A) 正确 B） 不正确按照二叉树的定义，具有3个结点的二叉树有_c____种。
A） 3 B） 4 C） 5 D） 6
一棵二叉树如图所示，其中遍历的序列为_b____。
A） abdgcefh B) dgbaechf C) gdbehfca D) abcdefgh
树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论_a____是正确的。
树的先根遍历序列与其对应的二叉树的先序遍历序列相同树的后根遍历序列与其对应的二叉树的后序遍历序列相同树的先根遍历序列与其对应的二叉树的中序遍历序列相同以上说法都不对深度为5的二叉树至多有_c____个结点。
A） 16 B） 32 C） 31 D） 10
在一非空二叉树的中序遍历序列中，根结点的右边_a____。
A） 只有右子树上的所有结点 B） 只有右子树上的部分结点
C） 只有左子树上的部分结点 D） 只有左子树上的所有对点树最适合用来表示__c___。
A） 有序的数据元素 B） 无序的数据元素
C） 元素之间具有分支层次关系的数据 D）元素之间无联系的数据任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序__a___。
A） 不发生改变 B） 发生改变 C） 不能确定 D） 以上都有不对实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用_d__存储结构。
A） 二叉链表 B） 广义表存储结构 C） 三叉链表 D） 顺序存储结构对一个满二叉树，m个树叶，n个结点，深度为h，则___d__。
A） n=h+m B) h+m=2n C) m=h-1 D) n=2h-1
如果某二叉树的前序为stuwv，中序为uwtvs，那么该二叉树的后序为_c____。
A) uwvts B) vwuts C) wuvts D) wutsv
t2
如图所示的t2是由有序树t1转换而来的二叉树，那么树t1有_c____个叶结点。
A) 4 B) 5 C) 6 D) 7
设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是__c___。
A) n在m的右方 B） n是m的祖先
C）n 在m的左方 D） n是 m的子孙线索二叉树是一种__c___结构。
A） 逻辑 B） 逻辑与存储 C） 物理 D） 线性二．填空题（将正确答案填在相应的空中）
1．一棵树如图所示，回答下面的问题：
棵树的根结点是_k1____。
这棵树的叶结点是__k2,k5,k4,k7___。
结点k3的度是_2____。
这棵树的度为___3__。
这棵树的深度是__4___。
结点k3的子女是__k5,k6,k7___。
结点k3的父结点是__k1___。
4,一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图所示，则该二叉树的链接表示形式为_____。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
t:
深度为k的完全二叉树至少有_____个结点。至多有_____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_____。
在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0==__n2+1___。
一棵二叉树的第i(i≥1)层最多有_____个结点；一棵有n(n>0)个结点的满二叉树共有_____个叶子和_____个非终端结点。
结点最少的树为_空____树，结点最少的二叉树为_空____树。
现有按中序遍历二叉树的结果为abc，问有__5___种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是_____。
根据二叉树的定义，具有三个结点的二叉树有_5____种不同的形态，它们分别是_____。
由如图所示的二叉树,回答以下问题:
其中序遍历序列为__dgbaechif___。
其前序遍历序列为__ abdgcefhi ___。
其后序遍历序列为__ gdbeihfca ___。
该二叉树的中序线索二叉树为_____。
该二叉树的后序线索二叉树为_____。
该二叉树对应的森林是_____。
已知一棵树如右图所示，其孩子兄弟表示为_____。
13．以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman树为_____，其带权路径长度为_____。
图一．单项选择题在一个图中，所有顶点的度数之和等于所有边数的_c____倍。
A）1/2 B) 1 C) 2 D) 4
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的__b___倍。
A) 1/2 B) 1 C) 2 D) 4
一个有n个顶点的无向图最多有__c___条边。
A) n B) n(n-1) C) n(n-1)/2 D) 2n
具有4个顶点的无向完全图有_a____条边。
A) 6 B) 12 C) 16 D) 20
具有6个顶点的无向图至少应有_a____条边才能确保是一个连通图。
A) 5 B) 6 C) 7 D) 8
在一个具有n个顶点的无向图中，要连通全部顶点至少需要__c___条边。
A) n B) n+1 C) n-1 D) n/2
对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_d____。
A) n B) (n-1)2 C) n-1 D) n2
对于一个具有n个顶点和e条边的无向图，若采用邻接表示，则表头向量的大小为__①_a__，所有邻接表中的结点总数是__②c___。
① A) n B) n+1 C) n-1 D) n+e
② A) e/2 B) e C) 2e D) n+e
已知一个图如下所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为
__①d___；按宽度搜索法进行遍历，则可能得到的一种顶点序列为__②b_ _。
① A) a,b,c,d,e,f B) a,c,f,e,b,d
C) a,e,b,c,f,d D) a,e,d,f,c,b
② A) a,b,c,d,e,f B) a,b,c,e,f,d
C) a,e,b,c,f,d D) a,c,f,d,e,b
已知一有向图的邻接表存储结构如图所示。
根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是_c____。
A) v1,v2,v3,v5,v4 B) v1,v2,v3,v4,v5 C) v1,v3,v4,v5,v2 D) v1,v4,v3,v5,v2
根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_b____。
A) v1,v2,v3,v4,v5 B) v1,v3,v2,v4,v5 C) v1,v2,v3,v5,v4 D) v1,v4,v3,v5,v2
采用邻接表存储的图的深度优先遍历算法类似于二叉树的_a____。
A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历采用邻接表存储的图的宽度优先遍历算法类似于二叉树的d_____。
A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用__d___。
A） 求关键路径的方法 B） 求最短路径的Dijkstra方法
C） 宽度优先遍历算法 D） 深度优先遍历算法二．填空题（将正确的答案填在相应的空中）
N个顶点的连通图至少_N-1____条边。
在无权图G的邻接矩阵A中，若（vi,vj）或<vi,vj>属于图G的边集合，则对应元素A[i][j]等于_1____，否则等于_0____。
在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_1____。
已知图G的邻接表如图1所示，其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4____，其从顶点v1出发的宽度优先搜索序列为___v1v2v5v4v3v6__。
已知一个图的邻接矩阵表示，计算第I个结点的入度的方法是_____。
已知一个图的邻接矩阵表示，删除所有从第I个结点出发的边的方法是_____。
查找一．单项选择题顺序查找法适合于存储结构为_b____的线性表。
A） 散列存储 B） 顺序存储或链接存储
C） 压缩存储 D） 索引存储对线性表进行二分查找时，要求线性表必须__b___。
A） 以顺序方式存储 B） 以顺序方式存储，且结点关键字有序排序
C） 以链接方式存储 D） 以链接方式存储，且结点关键字有序排序采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_c____。
A） n B) n/2 C) (n+1)/2 D) (n-1)/2
采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为__c___。
A) O(n2) B) O(nlog2n) C) O(n) D) O(log2n)
二分查找和二叉排序树的时间性能__b___。
A) 相同 B） 不相同有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，___c__次比较后查找成功。
A） 1 B） 2 C） 4 D） 8
设哈希表长m=14，哈希函数H(key)=key % 11。表中已有4个结点：
addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7
其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是__d___。
A） 8 B） 3 C） 5 D） 9
8．有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为__b___。
A） 35/12 B） 37/12 C） 39/12 D） 43/12
分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分__b___个结点最佳。
A） 10 B） 25 C） 6 D） 625
如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_d____查找方法。
A） 分块 B） 顺序 C） 二分 D） 散列
二．填空题顺序查找法的平均查找长度为_____；二分查找法的平均查找长度为_____；分块查找法（以顺序查找确定块）的平均查找长度为_____；分块查找法（以二分查找确定块）的平均查找长度为_____；哈希表查找法采用链接法处理冲突时的平均查找长度为_____。
在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____。
二分查找的存储结构仅限于_____，且是_____。
在分块查找方法中，首先查找_____，然后再查找相应的_____。
长度为255的表，采用分块查找法，每块的最佳长度是_____。
在散列函数H(key)=key % p中，p应取_____。
假设在有序线性表A[1..20]上进行二分查找，则比较一次查找成功的结点数为_10____，则比较二次查找成功的结点数为_5,15____，则比较三次查找成功的结点数为_2,7_12,18___，则比较四次查找成功的结点数为_1,3_,6,8,,11,13,16,19___，则比较五次查找成功的结点数为 _4,9,14,17,20____，平均查找长度为_3.7____。
对于长度为n的线性表，若进行顺序查找，则时间复杂度为__o(n)___；若采用二分法查找，则时间复杂度为_o(logn)____。
在散列存储中，装填因子α的值越小，则_发生冲突的机会越小____。
内排序一．选择填空题在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是_d____。
A） 希尔排序 B） 起泡排序 C） 插入排序 D） 选择排序设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_d____排序法。
A） 起泡排序 B） 快速排序 C） 堆排序 D） 基数排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是_a____。
A） 插入排序 B） 选择排序 C） 快速排序 D） 归并排序一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_b____。
A） 79，46，56，38，40，80 B） 84，79，56，38，40，46
C） 84，79，56，40，38 D） 84，56，79，40，46，38
一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为__c___。
A） 38，40，46，56，79，84 B） 40，38，46，79，56，84
C） 40，38，46，56，79，84 D） 40，38，46，84，56，79
一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为__a___。
A）16，25，35，48，23，40，79，82，36，72
B）16，25，35，48，79，82，23，36，40，72
C）16，25，48，35，79，82，23，36，40，72
D）16，25，35，48，79，23，36，40，72，82
排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为__c___。
A） 希尔排序 B） 起泡排序 C） 插入排序 D） 选择排序排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为__d___。
A） 希尔排序 B） 归并排序 C） 插入排序 D） 选择排序用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
（1）25，84，21，47，15，27，68，35，20
（2）20，15，21，25，47，27，68，35，84
（3）15，20，21，25，35，27，47，68，84
（4）15，20，21，25，27，35，47，68，84
则所采用的排序方法是__c___。
A） 希尔排序 B） 归并排序 C） 快速排序 D） 选择排序下述几种排序方法中，平均时间复杂度最小的是_a____。
A） 快速排序 B） 归并排序 C） 插入排序 D） 选择排序下述几种排序方法中，要求内存量最大的是__b___。
A） 快速排序 B） 归并排序 C） 插入排序 D） 选择排序快速排序方法在__c___情况下最不利于发挥其长处。
A） 要排序的数据量太大 B）要排序的数据中含有多个相同的值
C） 要排序的数据已基本有序 D） 要排序的数据个数为奇数
二．填空题在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_3____次。
在堆排序，快速排序和归并排序中，若只从存储窨考虑，则应首先选取_堆排序____方法，其次选取_快速排序____方法，最后选取归并排序_方法；若只从排序结果的稳定性考虑，则应选取_归并排序____方法；若只从平均情况下排序最快考虑，则应选取_快速排序____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取__堆排序____方法。
在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有__希尔排序、快速排序、堆排序___。
在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是_基数排序____，需要内存容量最多的是_归并排序____。
在堆排序和快速排序中，若原始记录接近正序或反序，则选用_堆排序____，若原始记录无序，则最好选用__快速排序___。
在插入和选择排序中，若初始数据基本正序，则选用_插入排序____；若初始数据基本反序，则选用__选择排序___。
对n个元素的序列进行起泡排序时，最少的比较次数是_n-1____。
