一、填空题
1、数据的逻辑结构描述的是数据元素之间的逻辑关系，通常有下列4类基本结构：集合、线性结构、树形结构和图状结构（或称为网状结构）。 2、栈顶的位置是随着 进栈和退栈 操作而变化的。
3、链表对于数据元素的插入和删除操作不需移动结点，只需改变相关结点的 指针 域的值。
4、在一棵树中， 叶子 结点没有后继结点。
5、在串S=\"structure\"中，以t为首字符的子串有 12 个。
6、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 顺序 存储结构。 7、具有256个结点的完全二叉树的深度为___ 9___。 8、二维数组a[4][5]（下标从0开始计，a有4*5个元素），每个元素的长度是2，则a[3][2]的地址是 1034 。(设a[0][0]的地址是1000，数据以行为主方式存储)。 9、中缀表达式a+b*3+4*（c-d）对应的前缀表达式为 ++a*b3*4-cd 。 10、在二叉树中，指针p所指结点为叶子结点的条件是_p→rchild==NULL && p→lchild==NULL 。
11、在串S=\"statistics\"中，以t为首字符的子串有 20 个。 12、数据结构中评价算法的两个重要指标是 时间复杂度 空间复杂度 。 13、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动 n-i+1 个元素。
14、空格串是指 由一个或多个空格组成的串 ，其长度等于 空格数 。 15、在单链表中设置头结点的作用是_头结点用来存放指向链表中首个结点的指针_。 16、顺序存储结构是通过__数组下标__表示元素之间的关系的;链式存储结构是通过_结点的指针域_表示元素之间的关系的。
17、在单链表p结点之后插入s结点的操作是： s->next=p->next;p->next=s; 。 18、INDEX（‘DATASTRUCTURE’， ‘STR’）= 5 。
19、设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为 9174 ;若以列序为主序顺序存储，则元素a[45,68]的存储地址为 8788 。
20、假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是 log2n+1 。 二、选择题
1、算法指的是（ ）
A．计算机程序 B．解决问题的计算方法
C．排序算法 D．解决问题的有限运算序列 2、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） A．O（1） B．O（n） C．O（m） D．O（m+n） 3、线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可 C．必须是连续的
D．和头结点的存储地址相连续 4、以下数据结构中，（ ）是非线性数据结构。 A．树 B．字符串 C．队 D．栈
5、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。
A. 不确定 B. n-i+1 C. i D. n-i
6、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 7、线性表是具有n个（ ）的有限序列（n>0）。
A．表元素 B．信息项 C．数据元素 D．数据项
8、若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行
concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))，其结果为（ ）。（说明：下标和位置索引均从1开始计）
A．ABC###G1234 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G0123 F．ABCD###1234 G．ABC###01234 9、在一棵高度为k的满二叉树中，结点总数为（ ）。 A．2k-1 B．2k C．2k-1 D．log2k + 1
10、深度为h的二叉树的第k层至多有（ ）个结点。(1= 12、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ ）。 A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 13、栈和队列的共同点是（ ）。 A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点 14、串的长度是指（ ）。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 15、数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。 A. 55 B. 45 C. 36 D. 16 16、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 17、具有10个叶结点的二叉树中有（ ）个度为2的结点. A．8 B．9 C．10 D．11 18、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2 19、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。 A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改 20、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 三、判断题 1、完全二叉树一定存在度为1的结点。.× 2、二叉树的遍历结果不是唯一的。√ 3、栈与队列是一种特殊操作的线性表。√ 4、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。√ 5、通常使用队列来处理函数或过程的调用。× 6、取线性表的第i个元素的时间同i的大小有关。× 7、顺序存储结构的主要缺点是不利于插入或删除操作。√ 8、算法的优劣与算法描述语言无关，但与所用计算机有关。× 9、数据结构的抽象操作的定义与具体实现有关。× 10、在顺序存储结构中，有时也存储数据结构中元素之间的关系。× 11、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。× 12、线性表就是顺序存储的表。× 13、所谓静态链表就是一直不发生变化的链表。× 14、程序一定是算法。× 15、顺序存储方式只能用于存储线性结构。× 16、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构× 四、应用题 已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 A、删除首元结点的语句序列是 (12) (11) (3) (14) 。 B、删除P结点的直接前驱结点的语句序列是 (10) (12) (8)（11） (3) (14) 。 C、删除尾元结点的语句序列是 (9) (11) (3) (14) 。 D、删除P结点的直接后继结点的语句序列是 (11) (3) (14) 。 E、删除P结点的语句序列是 (10) (12) (7) (3) (14) 。 (1) P = P->next; (2) P->next = P; (3) P->next = P->next->next; (4) P = P->next->next; (5) while(P != NULL) P = P->next; (6) while(Q->next != NULL) { P = Q; Q = Q->next; } (7) while(P->next != Q) P = P->next; (8) while(P->next->next != Q) P = P->next; (9) while(P->next->next != NULL) P = P->next; (10) Q = P; (11) Q = P->next; (12) P = L; (13) L = L->next; (14) free(Q); &&已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a．在P结点后插入S结点的语句序列是 (4) (1) b．在P结点前插入S结点的语句序列是 (7) (11) (8) (4) (1) c．在首表插入S结点的语句序列是 (5) (12) d．在尾表插入S结点的语句序列是 (9) (1) (6) (1))P->next=S; (2)P->next=P->next->next; (3)P->next=S->next; (4)S->next=P->next; (5)S->next=L; (6)S->next=NULL; (7)Q=p; (8)while (P->next!=Q) P=P->next; (9)while (P->next!=NULL) P=P->next; (10)P=Q; (11)P=L; (12)L=S; (13)L=P; 五、算法设计题 1、栈的顺序存储结构定义如下： #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ ElemType *base; ElemType *top; int stacksize; }SqStack; 入栈操作的函数原型为： Status Push( SqStack *S, ElemType e) //插入元素e为新的栈顶元素 请实现该函数算法。 Status Push(SqStack *S, ElemType e) { /*如果空间不够就重新分配*/ if ((*S).top-(*S).base > (*S).size) { (*S).base =(ElemType *)realloc((*S).base, ((*S).size+STACKINCREMENT)*sizeof(ElemType)); /*重新确定base指针 */ (*S).top = (*S).base + (*S).size; /*重新确定top指针 */ (*S).size+=STACKINCREMENT; } *(*S).top = e; (*S).top++; return OK; } 2、单链队列的存储结构定义为： typedef struct QNode { QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; 出队函数原型为： Status DeQueue( LinkQueue *Q, QElemType *e) //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR 请实现该函数算法。 Status DeQueue(SqQueue &Q,QElemType &e){/*若队列不空，则删除Q的队头元素，用e返回其值，并返回OK,否则返回ERROR*/ if(Q.rear==Q.front) return ERROR;/*队列空*/ e=Q.base[Q.front]; Q.front=(Q.front+1)%MaxQsize; return OK;} 3、串的堆分配存储结构定义为： typedef struct{ char *ch; int length; }HString; 串联接操作的函数原型为： Status Concat(HString *T, HString S1, HString S2) //用T返回由S1和S2联接而成的新串 请实现该函数算法。 Status Concat(HString &T,HString S1,HString S2) {//用T返回值由S1和S2联接而成的新串 if (T.ch) free(T.ch); //释放原有的空间 if (!(T.ch=(char *)malloc((S1.length+S2.length)*sizeof(char)))) exit(OVERFLOW); int i; for (i=0;i 求字串操作的函数原型为： HString SubString(HString *Sub, HString S, int pos, int len); //用Sub返回串S的第pos个字符起长度为len的字串。 //其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。 请实现该函数算法。 void SubString(HString *sub,HString s,int pos,int len) { //用sub返回串s的第pos个字符起长度为len的子串 //其中,1<=pos<=strlenth(s)且0<=len<=strlength(s)-pos + 1. int i,j; if(pos<1 || pos>s.length || len<0 || len>s.length-pos+1) { printf(\"SubString's Location error!\\n\"); exit(1); } if(sub->ch) free(sub->ch); //释放旧空间 if(!len) { sub->ch = NULL; sub->length = 0; } else { sub->ch = (char*)malloc((len+1)*sizeof(char)); for(i=0,j=pos-1;j<=pos+len-2;++i,++j) sub->ch[i] = s.ch[j]; sub->length = len; sub->ch[sub->length] = '\\0'; } } 因篇幅问题不能全部显示，请点此查看更多更全内容