第1章绪论
习题
1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题
（1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现
（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈
6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100;
while(y>0) if(x>100) {x=x-10;y--;} elsex++;
（2）for(i=0;i for(j=0;j （3）s=0; fori=0;i for(j=0;j s+=B[i][j]; sum=s; （4）i=1; while(i<=n) i=i*3; （5）x=0; for(i=1;i x++; （6）x=n;n108 C63.5 C1 C-1 C1 Cext=s;(*s).next=(*p).next; C．s->next=p->next;p->next=s->next; D．s->next=p->next;p->next=s; (14)在双向链表存储结构中，删除p所指的结点时须修改指针（）。 A．p->next->prior=p->prior;p->prior->next=p->next; B．p->next=p->next->next;p->next->prior=p; C．p->prior->next=p;p->prior=p->prior->prior; D．p->prior=p->next->next;p->next=p->prior->prior; (15)在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。 A．p->next=q;q->prior=p;p->next->prior=q;q->next=q; B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q; 2．算法设计题 （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中不允许有重复的数据。 voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){ pa=La->next;pb=Lb->next; Lc=pc=La;3 C想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。 A．x=top->data;top=top->link； B．top=top->link;x=top->link； C．x=top;top=top->link； D．x=top->link； （5）设有一个递归算法如下 intfact(intn){3 C0 C性表的链式存储结构D.栈 （11）用链接方式存储的队列，在进行删除运算时（ ）。 A.仅修改头指针B.仅修改尾指针 C.头、尾指针都要修改D.头、尾指针可能都要修改 （12）循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。 =rear+=(rear+1)%(m-1) =(rear+1)%=(rear+1)%(m+1) （13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。 A.(rear+1)%n====front C．rear+1==frontD.(rear-l)%n==front （14）栈和队列的共同点是（ ）。 A.都是先进先出B.都是先进后出 C.只允许在端点处插入和删除元素D.没有共同点 （15）一个递归算法必须包括（ ）。 A.递归部分B.终止条件和递归部分 C.迭代部分D.终止条件和迭代部分 （2）回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 根据提示，算法可设计为： 0’9’0’9’0’0’9’0’0’9’0’0’0’M-1]实现循环队列，其中M是队列长度。设队头指针front 和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。 （1）#defineM队列可能达到的最大长度 typedefstruct {elemtpdata[M]; intfront,rear; }cycqueue; （2）elemtpdelqueue(cycqueueQ) C100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。 A．808B．818 C．1010D．1020 （7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。 A．BA+141B．BA+180 C．BA+222D．BA+225 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A．13B．33 C．18D．40 （9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i （10）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。 A．i(i-1)/2+jB．j(j-1)/2+iC．i(j-i)/2+1D．j(i-1)/2+1 （11）设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（）。 A．(i-1)*n+jB．(i-1)*n+j-1 C．i*(j-1)D．j*m+i-1 （12）数组A[0..4,-1..-3,5..7]中含有元素的个数（）。 A．55B．45 C．36D．16 （13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。 A．(g)B．(d)C．cD．d （14）广义表((a,b,c,d))的表头是（），表尾是（）。 A．aB．()C．(a,b,c,d)D．(b,c,d) （15）设广义表L=((a,b,c))，则L的长度和深度分别为（）。 A．1和1B．1和3 C．1和2D．2和3 （1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。 模式串t的next和nextval值如下： j t串 next[j] nextval[j] 12 abcaabbabcab 0 0 （2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ①计算模式p的naxtval函数值； ②不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 ①p的nextval函数值为0110132。（p的next函数值为0111232）。 ②利用KMP(改进的nextval)算法，每趟匹配过程如下： 第一趟匹配：abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配：abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配：abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配：abcaabbabcabaacbacba (成功)abcabaa(i=15,j=8) （3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： ①存放该数组所需多少单元 ②存放数组第4列所有元素至少需多少单元 ③数组按行存放时，元素A[7,4]的起始地址是多少 ④数组按列存放时，元素A[4,7]的起始地址是多少 每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。 （1）242（2）22（3）s+182（4）s+142 (4)请将香蕉banana用工具H()—Head()，T()—Tail()从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) H（H（T（H（T（H（T（L））））））） （5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。 voidCount（） 是字符串输入结束标志 {InvertStore(A); A[i++]=ch;0’0’0’m,1..n]含有m*n个整数。 ①写一个算法判断a中所有元素是否互不相同输出相关信息(yes/no)； ②试分析算法的时间复杂度。 [题目分析]判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。 intJudgEqual(inga[m][n],intm,n) [算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1). 第5章树和二叉树 1．选择题 （1）把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A．唯一的Ｂ．有多种 C．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子 （2）由3个结点可以构造出多少种不同的二叉树（） A．2B．3 C．4D．5 （3）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250B．500 C．254D．501 （4）一个具有1025个结点的二叉树的高h为（）。 A．11B．10 C．11至1025之间D．10至1024之间 （5）深度为h的满m叉树的第k层有（）个结点。(1= k-1kh-1h A．mB．m-1 C．mD．m-1 （6）利用二叉链表存储树，则根结点的右指针是（）。
相关推荐：
loading