1.非空的循环单链表head的尾结点（由p所指向）满足（C ）。
A. p->next==NULL B .p==NULL C. p->next==head D. p==head
2.在一个链队中,假设f和r分别为队首和队尾指针,则删除一个结点的运算是（ C ）。 A.r=f->next; B.r=r->next C.f=f->next; D.f=r->next
3.在一个链队中,假设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 4.不带头结点的单链表head为空的判定条件是（A ）。 A.head==NULL B.head->next==NULL C.head->next==head D.head!=NULL 5.带头结点的单链表head为空的判定条件是（ B ）。
A.head==NULL B.head->next==NULL C.head->next==head D.head!=NULL 6.一个向量第一元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是（B ）。 A.110 B.108 C.100 D.120 7.在长度为n的顺序表的第I(1≤I≤n+1)个位置上插入一个元素，元素的移动次数为（ A ）。 A.n-I+1 B.n-I C.I D.I-1
8.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ C ）。
A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 9.若循环链表的结点具有数据域data和指针域next，H指向其头结点，该表具有一个结点的条件是（B ）为真值。
A.H= =H->next B.H= =H->next->next C.H->next D.!(H->next) 10.线性表采用链式存储时，结点的存储地址（ B）。
A.必须是不连续的 B.连续与否均可 C.必须是连续的 D.和头结点的存储地址相连续
二、LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){ Q=L;L=L->next;P=L; while (P->next) P=P->next;
P->next=Q; Q->next=NULL; }
return L; }// Demo PPT上讲过，答案略
三、表逆置的算法
四、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点指针，试编写算法在链表中删除指针s所指结点的前驱结点。
第三章
1.栈结构通常采用的两种存储结构是（A ）。
A.线性存储结构和链表存储结构 B.散列方式和索引方式
C.链表存储结构和数组 D.线性存储结构和非线性存储结构
2.判定一个栈st(最多元素为m0)为空的条件（ B）。
A.st->top!=0 B.st->top==0 C.st->top!=m0 D.st->top==m0 3.一个队列的入列序列是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 4.判定一个队列qu(最多元素m0)为空的条件是（ C）。 A.qu->rear-qu->front==m0 B.qu->rear-qu->front-1==m0
C.qu->front==qu->rear D.qu->front==qu->rear+1
7.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（B ）。 A.4 B.5 C.6 D.7 8.采用链表方式表示一个栈，便于结点的插入与删除。栈顶结点的插入与删除能在链表的（B）进行
A.任意位置 B.一端 C.两端 D.中间进行
9.由两个栈共享同一个向量空间的好处是（B ）。
A.减少存取时间，降低下溢发生的机率 B.节省存储空间，降低上溢发生的机率 C.减少存取时间，降低上溢发生的机率 D.节省存储空间，降低下溢发生的机率 10.栈的操作特点是（B ）。 A.先进先出 B.后进先出 C.两端操作 D.都不对
二、写出下列程序段的输出结果。 （栈的元素类型Selemtype为char,队列中的元素类型Qelemtype为char） (1) void main( ){ Stack S; char x, y;
InitStack ( S );
x = ‘c’; y = ‘k’;
Push( S , x); Push ( S, ‘a’ ); Push( S, y); Pop( S, x); Push( S, ‘t’); Push ( S, x); Pop( S, x); Push ( S, ‘s’);
while (!StackEmpty ( S )) {Pop( S, y); printf(y); }; printf(x); }
(2) void main( ){ Queue Q;
InitQueue( Q );
char x=‘e’, y=‘c’ ;
EnQueue(Q, ‘h’); EnQueue(Q, ‘r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ‘a’ ); while (!(QueueEmpty ( Q )){ DeQueue( Q, y); printf ( y ); }
printf (x);
)
三、简述以下算法的功能。 (1) void Demo1(SeqStack *S){ int I; arr[] ; n=0 ;
while ( StackEmpty(S)) arr[n++]=Pop(S); for (I=0, I< n; I++) Push(S, arr[I]); } //Demo1
(2) SeqStack S1, S2, tmp;
DataType x;
…//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)){ x=Pop(&S1) ; Push(&tmp,x); }
while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &S1,x); Push( &S2, x);
(3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型 SeqStack T; int I; InitStack (&T);
while (! StackEmpty( S))
if(( I=Pop(S)) !=m) Push( &T,I); while (! StackEmpty( &T)) { I=Pop(&T); Push(S,I); } }
(4)void Demo3( CirQueue *Q) { // 设DataType 为int 型 int x; SeqStack S; InitStack( &S);
while (! QueueEmpty( Q )) {x=DeQueue( Q); Push( &S,x);} while (! StackEmpty( &s))
{ x=Pop(&S); EnQueue( Q,x );} }// Demo3
(5) CirQueue Q1, Q2; // 设DataType 为int 型 int x, I , m = 0;
… // 设Q1已有内容， Q2已初始化过
while ( ! QueueEmpty( &Q1) )
{ x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); m++;} for (I=0; I< n; I++)
{ x=DeQueue(&Q2) ;EnQueue( &Q1, x) ; EnQueue( &Q2, x);}
第四章 串
2.串是一种特殊的线性表,其特殊性体现在（ D ）。
A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是个字符
3.为查找某一特定单词在文本中出现的位置，可应用的串运算是( D) 。 A.插入 B.删除 C.串联接 D.子串定位
4.函数Sub(s,I,j)的功能是返回串s中从第I个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(A )。
A.P=″SCIENCE″ B.P=″STUDY″ C.S=″SCIENCE″ D.S=″STUDY″
5.如下陈述正确的是（ A）。 A.串是一种特殊的线性表
B.串的长度必须大于0
C.串中元素只能是字母 D.空串就是空白串
6.利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int I),将串T插入到串S的第I个位置上。若I大于S的长度，则插入不执行。
解：算法如下：
void StrInsert(char *S, char *T, int I) {
//将串T插入到串S的第I个位置上 char *Temp;
Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 if(I<=strlen(S)) {
strcpy(Temp,&S[I]);//将第I位起以后的字符拷贝到临时串中
strcpy(&S[I], T);//将串T拷贝到串S的第I个位置处，覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 free( Temp ); } }
//以下提供验证程序
#include \"string.h\" #include \"stdio.h\" #include \"malloc.h\"
#define Maxsize 50 //假设静态顺序串的空间长度为100 void StrInsert(char *S, char *T, int I); void main()
{
char A[Maxsize]=\"I am a boy.\"; char B[Maxsize]=\"very cool \"; StrInsert( A,B,7); printf(\"%s\
}
void StrInsert(char *S, char *T, int I) {
//将串T插入到串S的第I个位置上 char *Temp;
Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 if(I<=strlen(S)) {
strcpy(Temp,&S[I]);//将第I位起以后的字符拷贝到临时串中
strcpy(&S[I], T);//将串T拷贝到串S的第I个位置处，覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 }
free( Temp ); }//程序结束
第六章 和二叉树
1. 请对下图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。
答案：
：
2. 已知一棵二叉树的前序遍历结果是ABECDFGHIJ，中序遍历的结果是
EBCDAFHIGJ，则它的后序遍历结果是（）。答案：EDCBIHHGFA
3. 分别写出下图所示各二叉树的前序、中序和后序序列。
答案：a)前序序列：12345 中序序列：24531 后序序列：54321
(b)前序序列：12345 中序序列：13542 后序序列：54321
?前序序列：123578 中序序列：17583624 后序序列：78563421
(d)前序序列：1247356 中序序列：472153869 后序序列：7425631 4. 深度为5的二叉树至多有（C）个结点。
A.16 B.32 C.31 D.10 5. 树最适合用来表示（C ）。
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 下列陈述中正确的是(D )。
A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左
右之分
C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有
左右之分
三个结点的二叉树的形态有（ C）种。 A.3 B.4 C.5 D.6
第七章 图
1. 一个有n个顶点的无向图最多有（C ）条边。
A.n B.n(n-1) C.n(n-1)/2 D.2n
2. 已知一个有向图如右所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS
序列为（D ）。
A.ABECDF B.ACEBFD C.ACDFEB D.ACEDBF 3. 如下图所示，从A出发的广度优先遍历结果为（A ）。
A.ABCDEF B.ABEFCD C.ABCDFE D.ABCEDF 4. 其余大题看PPT上的例题和上课是所举例题
第九章 查找
1.顺序查找法适合于存储结构为（ B）的线性表。
A.散列存储 B.顺序存储或链接存储 C.压缩存储 D.索引存储 2.对线性表进行二分查找时，要求线性表必须（ C）。
A.以顺序方式存储 B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（C ）。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 4.长度为255的表，采用分块查找法，每块的最佳长度是（B ）。
A.14 B.15 C.16 D.17
5.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是（D ）。
A.顺序查找法 B.二分查找法 C.分块查找法 D.哈希表查找法 6.如果要求一个线性表既能较快地查找，又能适应动态变化地要求，可以采用（A ）查找方法。
A.分块 B.顺序 C.二分 D.散列
7.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是( A )。
A.小于 B.大于 C.等于 D.不小于 8.折半查找算法的时间复杂度是（D）。
A.O(n2) B.O(n) C.O(nlog2n) D.O(log2n) 9.适于对动态查找表进行高效率查找的组织结构为（C ）。
A.有序表 B.分块有序表 C.二叉排序树 D.线性链表
设有序表为(a,b,c,e,f,g,I,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程 解： b的查找过程如下(其中括号表示当前查找区间，圆括号表示当前比较的关键字) 下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较： [a b c d e f (g) h I j k p q] 第二次比较： [a b ?d e f] g h I j k p q 第三次比较： [a(b)]c d e f g h I j k p q 经过三次比较，查找成功。
g的查找过程如下： [a b c d e f (g) h I j k p q] 一次比较成功。
n的查找过程如下：
下标： 1 2 3 4 5 6 7 8 9 10 11 12 13 第一次比较： [a b c d e f (g) h I j k p q] 第二次比较： a b c d e f g [h I (j) k p q] 第三次比较： a b c d e f g h I j [k (p) q] 第四次比较： a b c d e f g h I j [k] p q] 经过四次比较，查找失败。 课件上的关于哈希表的存放问题
第十章 内部排序
1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（D ）。
A.希尔排序 B.起泡排序 C.插入排序 D.选择排序 2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用
（C）排序法。
A.起泡排序 B.快速排序 C.堆排序 D.基数排序 3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（A ）。
A.插入排序 B.选择排序 C.快速排序 D.归并排序 4. 一组记录的排序码为（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，46，40，38 D.84，56，79，40，46，38 7.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做多少次关键码比较。 （ C ）
A.2 B.3 C.4 D.5
8.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是（A ）。 A.堆排序< 快速排序< 归并排序 B.堆排序< 归并排序< 快速排序
C.堆排序> 归并排序> 快速排序 D.堆排序> 快速排序> 归并排序
9.下列排序算法的时间复杂度最小的是（ D）。
A.冒泡排序 B.希尔排序 C.简单选择排序 D.归并排序
10.对记录的关键字集合Key={50，26，38，80，70，90，8，30，40，20}进行排序，各趟排序结束时的结果为
其使用的排序方法是（C ）。
A.快速排序 B.基数排序 C.希尔排序 D.归并排序
5. 下面给出了冒泡排序算法，请填写算法中的空框，使算法正确。
typedef struct{ int key；
datatype info;//设datatype已经定义
}node；
void BubbleSort ( node R[])//R中元素个数为n个 {
int I,j;
Boolean flag； node X；
for(I=1;I<=n-1;I++) {
___________1.
for (j=n-1;j>=I;j--)____________2 if(________3.)＜R[j].key {
flag =TURE； X=R[j]; __________4..; R[j＋1]= X; }
if(_________5)return; }// 算法结束
每种排序的每趟结果需要掌握（就是对排序方法的掌握）
因篇幅问题不能全部显示，请点此查看更多更全内容