1、复习题库答案讲解数据结构习题习题一一、选择题1、算法分析的两个主要方面是： （ B ） A正确性和简明性 B时间复杂度和空间复杂度 C数据复杂性和程序复杂性 D可读性和文档性2、在数据结构中，从逻辑上可以把数据结构分成（C）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D逻辑结构和存储结构3、计算机算法具备输入、输出和（C ）等5个特性： A有穷性、确定性和稳定性 B可行性、可移植性和可扩充性 C有穷性、确定性和可行性 D易读性、稳定性和安全性4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的输人与输出关系 C分析算法的有效性以求改进 D分析算法的易懂性
2、二、填空题1、数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2、线性结构中元素之间存在一对一 的关系，树形结构中元素之间存在一对多 的关系，图形结构中元素之间存在多对多 的关系。3、_数据项_是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项_。4、数据的_存储结构_指数据元素及其关系在计算机存储器内的表示。存储结构_是逻辑结构在计算机里的实现，也称之为映像。5、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组_有限序列_，其中每个指令表示一
3、个或多个操作。 三、问答题 1、用大O形式写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; O（n） 2、写出以下算法的时间复杂度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; jt; j+） for（k=0；kn；k） cijaik*bkj; O(mnt)习题二一、选择题 1在一个长度为n的顺序表中删除第i个元素（0iNext) & (L=L-Prior)。三、问答题1对链表设置头结点的作用是什么？（至少说出两条好处）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置
4、上的操作就和在表的其他位置上操作一致，无需进行特殊处理。 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就一致了。2在单链表、双链表中，如果仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？（不能）3如果频繁地对一个线性表进行插入和删除操作，那么该线性表应该采用何种存储结构？为什么？（采取链式存储结构）顺序存储：插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量结点，其效率较低；由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大
5、长度预先分配空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的存储空间而造成溢出。四、程序设计题1有一个带头结点的单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域值为x的结点个数。int count_list(linklist *head ) /*在带头结点的单链表中计算所有数据域为x的结点的个数*/ linklist *p; int n; p=head-next; /*p指向链表的第一个结点*/ n=0; while (p!=NULL) if (p-data=x) n+;p=p-next; return
6、(n); /*返回结点个数*/ /*count_list*/2设计一个算法，删除单链表L中值为x的结点的直接前驱结点。DeleteNode( Node* L, int x) Node* p,q,r; p = q = r = L; while(p-next ! = NULL) p = p -next; if(p-data = x) break; r = q; q = p; delete q; r-next = p; 3设计一个算法，将一个不带头结点的单链表L（至少有一个结点）逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。void reverse_list( li
7、nklist * head ) /*逆置带头结点的单链表*/ linklist *s, *p; p=head-next; /*p指向线性表的第一个元素*/ head-next=NULL; /*初始空表*/ while ( p != NULL ) s=p; p=p-next;s-next=head-next; head-next=s; /*将s结点插入逆表*/ /*reverse_list*/4在一个带头结点的单链表中，头指针为head，它的数据域的类型为整型，而且按由小到大的顺序排列，编写一个算法insertxlist（），在该链表中插人值为x的元素，并使该链表仍然有序。linklist *i
8、nsertx_list(linklist *head, int x) /*在带头结点的单链表中插入值为x的元素，使该链表仍然有序*/ linklist *s, *p, *q; s=(linklist *)malloc(sizeof(linklist); /*建立数据域为x的结点*/ s-data=x; s-next=NULL; if (head-next=NULL | xnext-data ) /*若单链表为空或x小于链表第一个结点的数据域*/ s-next=head-next; head-next=s; else q=head-next;p=q-next; while( p != NULL
9、& xp-data ) q=p; p=p-next; s-next=p; q-next=s; /*if*/ /*insertx_list习题三一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（C）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a2判定一个栈S（最多元素为MaxSize）为栈满的条件是：（ D ） AStop!= -1 BStop=-1 CStop=MaxSize-1 DStop!=MaxSize-13若一进栈序列为1，2，3，n，其出栈序列为P1,P2,P3,Pn，如果Pn=n,则Pi （1inext=s；r=s
10、； Br-next=s；f=s； Cs-next=r；r=s； Ds-next=f；f=s；5若用一个大小为8的一维数组来实现循环队列，且当前front和rear的值分别为4和1，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别是（B）： A3和5 B5和3 C2和6 D6和26判断一个循环队列Q（最多元素为MaxSize）为空的条件是：（A ）AQ-front=Q-rear BQ-front=（Q-rear +1）%MaxSize CQ-front!=Q-rear DQ-front!=（Q-rear +1）%MaxSize 7向一个带头结点、栈顶指针为top的链栈中插人
11、一个*S结点的时候，应当执行语句（ C ）。 Atop-next=S； BS-next=top；top=S； CS-next=top-next；top-next=S； DS-next=top；top=S-next；8在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ C ）。 Afrontfront-next BS-next=rear；rear=S Crear-next=S；rear=S DS-next=front；frontS9栈与队列都是（C ）。 A链式存储的线性结构 B链式存储的非线性结构 C限制存取点的线性结构 D限制存取点的非线性结构10若进
12、栈序列为l，2，3，4，则（ C ）不可能是一个出栈序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l11在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ B ）结构。 A堆栈 B队列 C数组 D线性表二、填空题 1栈和队列的共同点是都是限制存取点的线性结构。2通常元素进栈的操作是先进后出或后进先出 。3栈（stack）是限定在表尾 一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为栈顶_，而另一端称为栈底_。不含元素的栈称为_空栈_
13、。4队列（Queue）也是一种特殊的线性表_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾_，允许删除的一端称为队头_。5队列中允许进行删除的一端称为队头_；允许进行插入的一端称为_队尾_。三、问答题1设有一个数列的输入顺序为abcdef，若采用栈结构，并以J和C分别表示进栈和出栈操作，试问下列输出序列是否是合法序列？如是，请用进栈和出栈操作表示其合法序列。（1）能否得到输出顺序为cbefda的序列？J(a),J(b),J(c),C( ),C( ),J(d),J(e),C( ),J(f),C( ),C( ),C( )（2）能否得
14、到输出顺序为aedfbc154623的序列？不能2设输入元素为4、5、6、B、A，入栈次序为456BA，元素经过栈后到达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？3假设Q010是一个线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 （1）d，e，b，g，h入队（2）d，e出队（3）i，j，k，l，m入队（4）b 出队（5）n，o，p入队4设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序。14种A、B、C、D A、B、D、C A、C、B、D A、C、D、B A、D、C、B
15、B、A、C、D B、A、D、C B、C、A、D B、C、D、A B、D、C、AC、B、A、D C、B、D、A C、D、B、A D、C、B、A四、程序设计题1假设表达式中有三种括号：圆括号“（）”、方括号“ ”和花括号“ ”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。#include stdio.h#include stdlib.h#define FALSE 0#define TRUE 1#define LEN sizeof( struct node )struct node char data; struct node *next;typedef st
16、ruct node *stack;void push_stack(stack *, char );int pop_stack(stack *);void main() stack s; int valid=TRUE; char ch,symble;symble=getchar(); s=NULL; push_stack(&s, #); while (symble != # ) & (valid =TRUE) ) if ( symble !=( & symble !=) & symble != & symble != & symble != & symble != ) symble=getcha
17、r(); else if (symble=( | symble= | symble= ) push_stack(&s, symble ); symble=getchar(); else if ( s=NULL ) valid=FALSE; else ch=pop_stack(&s); if ( (ch=( & symble=) | (ch= & symble=) | ch=( & symble=) ) valid=TRUE; symble=getchar(); else valid=FALSE; if ( valid = TRUE ) printf( The string is valid.
18、n); else printf(The string is valid. n);void push_stack( stack *topptr, char ch ) stack newptr; newptr=(struct node * ) malloc( LEN ); newptr-data=ch; newptr-next=*topptr; *topptr=newptr;int pop_stack( stack topptr ) stack tempptr; char popvalue; if (topptr!=NULL ) tempptr=topptr; popvalue=topptr-da
19、ta; topptr=topptr-next;free( tempptr ); return popvalue; else return 0;习题四一、选择项4设有两个串 S2，S1，那么求串S2在S1 中首次出现的位置的运算称为：（ C ） A求子串 B求串长 C模式匹配 D串连接4设有串S=Computer，则其子串的数目是（ B ）。 A36 B37 C8 D94下列是C语言中“ASDF567HJKL”子串的是： （ C ） AASDF BDF56 C“F567HJ” D“DFHJ”5空串与空格串（ B ）。 A相同 B不相同 C可能相同 D无法确定二、境空题1串是由零个或多个字符组成的
20、有限序列。通常记作：s“c1，c2，cn”(n=0)，其中，S称为串名_；串中的Ci（1=i=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是串值_即串S的内容。2串中字符的个数称为串的长度_。3不含有任何字符的串称为空串_，它的长度为_0_。4由一个或多个空格构成的串称为空白串_，它的长度为所含空格的个数_。5串中任意多个连续字符组成的子序列称为该串的字串_；包含字串_的串称为主串。三、问答题1、现有串s1=ABCD123，s2=abcde，假设函数con(x,y)返回x和y串的连接串，函数subs(s,i,j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len(s)
21、返回串s的长度，求：（1）L1=subs(s1,2,len(s2) ( BCD12）（2）L2=subs(s1,len(s2),2) ( 12)(3)con(L1,L2) (ABCD123abcde)四、程序设计题l编写算法实现将窜S1中的第 i个字符到第 j个字符之间的字符(不包括第 i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为： define MAXSIZE 81 struct string int len； char chMAXSIZE； stringtype；void replace (stringtype s1, int i, int j, stringtype
22、s2) stringtype s100; int h,k; if ( i=h & is1.len & js1.len ) for (h=1; h=i; h+ ) s.chh=s1.chh; /*把s1的前i个字符赋值给s*/ s.len=i; h=1; while(hs2.len) /*连接串s2*/ s.chs.len+h=s2.chh; h+; s.len=s.len+s2.len; for ( k=s.len+1; h=j; h=s1.len; h+,k+ ) s.chk=s1.chh; /*将s1串中从第j个字符开始到结束的字符连接到s串*/ s.len=k; s.chs.len=0;
23、 return(s);习题五一、选择题 l数组常用的两种基本操作是（ D ）。A建立与查找 B删除与查找 C插人与索引 D查找与修改2对稀疏矩阵进行压缩存储，常用的两种方法是（ B ）。A二元组和散列表 B三元组和十字铸表 C三角矩阵和对角矩阵 D对角矩阵和十字链表3数组A中，每个数据元素的长度为2个字节，行下标m从1到10，列下标n从1到8，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是：（D ） A20 B80 C240 D1604数组A中，每个数据元素的长度为3个字节，行下标m从1到8，列下标n从1到10，从首地址SA开始连续存放在存储器内，该数组按行存储时，元素A83
24、的起始地址是：（D） ASA+222 BSA+141 CSA+44 DSA+2195若广义表L满足Head（L）= Tail（L），则广义表L为：（ A ） A（） B（） C（），（） D（），（），（）6广义表(a)的表头是（ C ）。 A（ ） Ba C（a） D（a）7广义表（a）的表尾是（ A ）。 A（） Ba C（a） D（a）8广义表（a），a）的表头是（ C ）。 A（ ） Ba C（a） D（a）9广义表（a），a）的表尾是（ C ）。 A( ) Ba C（a） D（a）10广义表（a，b，c）的表头是（ A ）。 Aa B（a） Ca，b D（a，b）11广义表（a，b，c）的表尾是（ B ）。 Ab，c B（b，c） ab，c D（a，b，c）二、填空题9 head（），（）是 （） ，tail（），（）是 （） ，表的长度是2 。10 head（(a)，(b),c)，(d)）是 （a） ，tail（(a)，(b),c)，(d)）是(b),c),(d) 。11现有广义表L=（(a)，(b),
