数据结构C语言版(崔近平 王霞)

1、第一章绪论一、选择题1、( B)是数据的基本单位。  A) 数据结构 B)数据元素 C)数据项 D)数据类型2、以下说法不正确的是( )。  )数据结构就是数据之间的逻辑结构。  )数据类型可看成是程序设计语言中已实现的数据结构。)数据项是组成数据元素的最小标识单位。  )数据的抽象运算不依赖具体的存储结构。3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（）等5个特性。A)可执行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性4、一般而言，最适合描述算法的语言是( )。 A)自然语言 B)

2、计算机程序语言 C)介于自然语言和程序设计语言之间的伪语言 D)数学公式5、通常所说的时间复杂度指( )。A)语句的频度 B)算法的时间消耗C)渐近时间复杂度 D)最坏时间复杂度6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明( )。  A)对于任何数据量，A算法的时间开销都比B算法小  B)随着问题规模n的增大，A算法比B算法有效  C)随着问题规模n的增大，B算法比A算法有效  D)对于任何数据量，B算法的时间开销都比A算法小7、算法分析的目的是（ ）。A)找出数据结构的合理性 B)研究算法中的输入和输出的关系C)分析算法的

3、效率以求改进 D)分析算法的易懂性和文档性8、下面程序段的时间复杂度为（ ）。 for( i=0; i<m; i+) for( j=0; j<n; j+) aij=i*j;A)O(m2) B) O(n2) C) O(m*n) D) O(m+n)9、下面算法的时间复杂度为( )。 int f( int n ) if ( n=0 | n=1 ) return 1; else return n*f (n-1); A) O(1) B) O(n) C) O(n2) D) O(n!)二、填空题1、数据的( )结构依赖于计算机语言。2、在线性结构中，第一个结点（ ）前驱结点,其余每个结点有且只有

4、（ ）个前驱结点；最后一个结点（ ）后继结点；其余每个结点有且只有（ ）个后继结点。3、在树形结构中,树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结点没有（ ）结点，其余每个结点的后继结点可以（ ）。 4、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着( ) 、（ ）和（ ）的关系。 5、评价一个算法优劣的两个主要指标是（ ）和（ ）。6、数据的逻辑结构被分为( )、( )、( )和( )四种。7、数据的存储结构被分为( )、（ ）、（ ）、（ ）四种.8、算法的时间复杂度除了与问题的规模有关外，还与输入实例的( )有关。三、问答题与算法题1、 简述下列概

5、念：数据元素：数据结构：数据类型：数据的逻辑结构及其4种类型：数据的存储结构及其4种方式：2、设两个算法在同一台机器上执行，其执行时间分别是 n2和2 n ，要使前者快于后者，n至少需要多大？2、有时为比较两个同数量级的算法优劣，须突出主项的常数因子，而将低次项用”O”记号表示。如：设T1 ( n ) = 1.39 n log n + 100 n + 256 = 1.39 n log n + O ( n ) ; T2 ( n ) = 2.0 n log n -2 n = 2.0 n log n O( n ) ;这两个式子表示，当n足够大时，T1 ( n )优于T2 ( n )，因为前者的系数因

6、子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣。 (1 ) T1 ( n ) = 5n 2 -3 n +60 log n ; (2 ) T2 ( n ) = 3 n 2 +1000 n + 3 log n ; (3 ) T3 ( n ) = 8 n 2 + 3 log n ; (4 ) T4 ( n ) = 1.5 n 2 + O ( n ) 。4、计算执行下面程序段时，执行S语句的次数为。 for(i=1; i<=n; i+) for( j=1; j<=i; j+) S;第二章线性表一、 选择题1、线性表是具有n个（）的有限序列。 A) 数据项；B

7、) 数据元素；C) 数据对象；D) 表元素。2、以下关于线性表的说法不正确的是( )。 A) 线性表中的数据元素可以是数字、字符、记录等不同类型。B) 线性表中包含的数据元素个数不是任意的。  C) 线性表中的每个结点都有且只有一个直接前趋和直接后继。  D) 存在这样的线性表：表中各结点都没有直接前趋和直接后继。3、线性表的顺序存储结构是一种( )的存储结构。  A) 随机存取  B) 顺序存取 C) 索引存取  D) 散列存取4、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。A) 基地址  B) 结点大小 C

8、) 线性表大小 D) 基地址和结点大小5、下面关于线性表的叙述中，错误的是哪一个？（ ）A) 线性表采用顺序存储，必须占用一片连续的存储单元。B) 线性表采用顺序存储，便于进行插入和删除操作。C) 线性表采用链接存储，不必占用一片连续的存储单元。D) 线性表采用链接存储，便于插入和删除操作。6、线性表采用链表存储时其存储地址要求（）。A) 必须是连续的；B) 部分地址必须是连续的；C) 必须是不连续的；D) 连续和不连续都可以。7、一个长度为n的顺序存储线性表中，向第i个元素(1in+1)之前插入一个新元素时，需要从后向前依次后移( )个元素。A) n-i B) n-i+1 C) n-i-1

9、D) i8、( )运算中，使用顺序表比链表好。 A) 插入 B) 删除 C) 根据序号查找 D) 根据元素值查找9、个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。  A) O(1)   B) O(n)   C) O(n2)  D) O(log2n)10、在一个长度为n的顺序存储线性表中，删除第i个元素(1in+1)时，需要从前向后依次前移( )个元素。A) n-i B) n-i+1 C) n-i-1 D) i11、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找

10、每个元素的概率都相等）为( )。A) n B) n/2 C) (n+1)/2 D) (n-1)/212、在一个带头结点单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A) HL = p; p->next = HL; B) p->next = HL; HL = p; C) p->next = HL; p = HL; D) p->next = HL->next; HL->next = p;13、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( )。 A) q->next = p->next ;

11、p->next = q; B) p->next = q->next; q = p; C) q->next = p->next; p->next = q; D) p->next = q->next ; q->next = p;14、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行( )。A) p = q->next ; p->next = q->next; B) p = q->next ; q->next = p;C) p = q->next ; q->next = p->nex

12、t; D) q->next = q->next->next; q->next = q;15、在双向链表指针p所指的结点前插入一个指针q所指的结点操作是（ ）。A) p->Prior=q;q->Next=p;p->Prior->Next=q;q->Prior=q；B) p->Prior=q;p->Prior->Next=q;q->Next=p;q->Prior=p->Prior;C) q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p-

13、>Prior=q;D) q->Prior=p->Prior;q->Next=q;p->Prior=q;p->Prior=q;16设双链表的结点的存储结构如下：删除链表中指针p所指结点的两步主要操作是：Llink Data Rlinkp( )， ( )。二、 填空题1、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为（）,在给定值为x的结点后插入一个新结点的时间复杂度为（）。2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成（）和（）。3、顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示

14、元素之间的关系的。4、对于双向链表,在两个结点之间插入一个新结点需修改( )个指针，单链表为( )个。5、循环单链表的最大优点是( ) 。6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在( )结点的next域中。7、带头结点的双循环链表L为空表的条件是（）。8、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用( )存储结构。9、求顺序表和单链表的长度算法的时间复杂度分别是 ( )和 ( )。10、顺序表存储结构的优点是( )、( )、( )；缺点是 ( )。11、单链表存储结构的优点是( )、 ( )；缺点是

15、 ( )、 ( )。12、在单链表中，设置头结点的作用是 ( ) 。13、链接存储的特点是利用( )来表示数据元素之间的逻辑关系。14、带头结点的双循环链表L为空表的条件是：( )。15、以下算法的功能是：在一个非递减的顺序表中，删除所有值相等的多余元素。在画线处填上适当的语句，将程序补充完整。 # define maxlen 100 typedef struct elemtype a maxlen ; int length ; sqlist ;void delequil ( sqlist & S ) int j=1 , i = 2 ; while ( _ ) if ( S.a i !

16、= S.a j ) _ ; _ ; i + ; 三、 问答题与算法题1、试描述头指针、头结点、首结点的区别、并说明头指针和头结点的作用。2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?3、为什么在单循环链表中设置尾指针比设置头指针更好?4、下述算法的功能是什么?LinkList ABC(LinkList L) / L 是无头结点单链表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; 5、写出下图

17、双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。结点结构为：(prior,data,next) 6、Void AA(SqList &L, int i, int x) if(i>=1&&i<=Length(L) FOR(j= Length (L);j>=i;j - -) Aj+1=Aj; Ai=x; else exit(ERROR); 假定调用该算法时线性表L的内容为（15，26，37，48，55），i为3,x为51，则调用返回后该单链表的内容变为什么?7、重写建立单连表的算法CreatList_L(Linklist &L,in

18、t n )，要求顺序输入n个元素的值(即先输入a1,a2.).CreatList_L(LinkList &L ； int n)8、设顺序表L是一个递减有序表，试写一算法，插入元素x，插入后仍保持L的有序性。 Void sinsert(Sqlist &S, int x) 9、写一算法，在带头结点的单链表上实现线性表的求表长ListLength(L)运算。int ListLength(LinkList L)10、写出从一个带头结点的单链表中删除其值等于给定值x的结点的算法函数。 Int delete(LinkList &L, int x) 11、已知递增有序的两个带头结点的

19、单链表La，Lb分别存储了一个非空集合A,B。设计算法实现求两个集合的并集的运算A=AB void mergelist(linklist &La, linklist Lb)12、设计算法将不带表头结点的单向链表就地逆转。13、删除整数数组中值相等的多余整数(只保留第一次出现的那个整数)。 Void delDuplicate(int A，int & n)第三章 栈和队列一、 选择题1、对于栈操作数据的原则是（ ）。A) 先进先出 B) 后进先出 C) 后进后出 D) 不分顺序2、一般情况下，将递归算法转换成非递归应通过设置（）实现。A) 数组；B) 线性表；C) 队列；D) 栈。

20、3、栈和队列的共同点是（ ）A) 都是先进后出 B) 都是先进先出C) 只允许在端点处插入和删除元素D) 没有共同点4、个栈的入栈序列是abcde，则栈的不可能的输出序列是( )。  A) edcba B) decba C) dceab D) abcde5、在对栈的操作中，能改变栈的结构的是( )。  A) StackLength(S)  B) StackEmpty(S) C) GetTop(S) D) ClearStack(S)6、在一个栈顶指针为HS的(不带头结点)链栈中将一个S指针所指的结点入栈,执行()。   A) HS->next=s;

21、  B) S->next=HS->next; HS->next=s;  C) S->next=HS; HS=s;   D) S->next=HS; HS=HS->next;7、若已知一个栈的入栈序列是1，2，3，n，其输出序列是p1,p2,p3，pn，若p1=n，则pi=( )。   A) I B) n-i C) n-i+1 D) 不确定8、若用一个大小为的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为和，当从队列中删除一个元素，再加入两个元素后，尾指针rear和头指针front的值分别是（）。A

22、) 和；B) 和；C) 和；D) 和。9、输入序列为ABC，可以变为BAC时，经过的栈操作为（ ）A)push,pop,push,pop,push,pop B)push,push,push,pop,pop,pop C)push,push,pop,pop,push,pop D)push,pop,push,push,pop,pop10、设用一个大小m=60的顺序表Am表示一个循环队列，如果当前的尾指针rear=32，头指针front15, 则当前循环队列的元素个数是( )。 A) 42 ；B) 16 ；C) 17 ；D) 41 。11、设用顺序表an表示循环队列，头、尾指针分别为front和rea

23、r，则判断队列为空的条件是（ ），判断队列满的条件是（）。（1）A) a.front +1= =a.rear ； B) a.front = = a.rear +1；C) a.front = = 0 ； D) a.front = = a.rear。（2） A) (a.rear -1) % n = a.front ； B) (a.rear +1) % n = a.front；C) a.rear =( a.front-1) % n； D) a.rear = (a.front +1) % n 。12、循环队列存储在数组A0.m中，则入队时的操作为（ ）。A) rear=rear+1 B) rear=(

24、rear+1) mod (m-1) C) rear=(rear+1) mod m D) rear=(rear+1)mod(m+1) 13、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该是一个（）结构。A) 栈； B) 队列； C) 数组； D) 线性表。14、设栈用向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。Atop:=top+1; V top:=x B. V top:=x; top:=top+1 C. top:=top-1; V top:=x D.

25、V top:=x; top:=top-115、 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top216、 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top2二、 填空题

26、1、在栈中，可进行插入和删除操作的一端称( )。2、在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。3、栈的特点是( )，队列的特点是（ ）。4、由于链栈的操作只在链表头部进行，所以没有必要设置()结点。5、带头结点的单链表L是空表的条件是（ ）；顺序栈S是空栈的条件是（ ）；顺序栈S满的条件是（ ）；不带头结点的链栈L是空栈的条件是（ ）；循环队列Q是空队列的条件是（ ）；循环队列Q是满队列的条件是（ ）6、用数组Q（其下标在0n-1之间，共有n个元素）表示一个循环队列，front 为当前队头元素

27、的前一个位置，rear为队尾元素的位置，假设队列中的元素个数总小于n，则求队列中元素个数的公式是（）。7、设元素入栈的顺序是、3、n ，则所有可能的出栈序列共有（）种。8、在具有n个单元的循环队列中，队满时共有（）个元素。9、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是( )，而栈顶指针值是( )H。(设栈为顺序栈，每个元素占4个字节)10、用PUSH表示入栈操作，POP 表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的PUSH和POP的操作串为(

28、 )。 三、 问答题与算法题 1、 设将整数1，2，3，4依次进栈，若入、出栈次序为Push(s,1), Pop(s,x1),Push(s,2),Push(s,3), Pop(s,x2), Pop(s,x3),Push(s,4), Pop(s,x4 ),则出栈的数字序列为何?2、设用不带头结点的单链表表示栈，请分别写出入栈和出栈的算法。(1) int push_L(Linkstack &s SelemType e) (2) int pop_L(Linkstack &s SelemType &e) 3、假设用带头结点的单循环链表表示队列，并设置一个指向尾结点的指针（无头指

29、针），请分别写出队列的入队和出队算法。(1)int EnQueue_L(Queueptr &QL QelemType e) (2)int DeQueue_L(Queueptr &QL QelemType &e)4、指出下述程序段的功能是什么? (1) void abc1(Stack &S) int i， arr64 , n=0 ; while (! StackEmpty(S) Pop(S，e);arrn+=e;for (i=0, i< n; i+) Push(S, arri); (2) Void abc2 (Stack S1, Stack &am

30、p; S2); initstack(tmp);while ( ! StackEmpty (S1) pop(S1,x);Push(tmp,x); while ( ! StackEmpty (tmp) ) Pop( tmp,x); Push( S1,x); Push( S2, x);(3) void abc3( Stack &S, int m)  InitStack (T); while (! StackEmpty( S) Pop(S,e); if( e!=m) Push( T,e); while (! StackEmpty( T)Pop(T,e); Push(S,e);(4)

31、void abc4( Queue &Q)InitStack( S);while (! QueueEmpty( Q )DeQueue( Q,x); Push( S,x);while (! StackEmpty( S) Pop(S,x); EnQueue( Q,x );(5) void invert1( LinkList &L)。 p=L;initstack(S); while(p) /链表中的元素全部进栈push(S,p->data); p=p->next;p=L; /利用原来的链表只修改数据域的值（反序）while(!stackempt(S) pop(S,e); p

32、->data=e; p=p->next;return OK; 5、回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的用带头结点的单链表表示的字符串是否为回文。 Int hw1(linklist L) 6、写一个将不带头结点的链栈S中所有结点均删去的算法void ClearStack( LinkStack &S)。7、写一个返回不带头结点的链栈S中结点个数的算法 int StackSize( LinkStack S).int Stacks

33、ize( LinkStack S)。8、利用栈操作，写一个算法把一个不带头结点的链表的元素反序存放（同第二章12题，这里要求利用栈操作）。void invert2( LinkList &L)。9、试将下列递归过程改写为非递归过程。 void test(int &sum) int x； scanf(x)； if(x=0) sum=0 else test(sum); sum+=x; printf(sum)； 10、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例

34、如：234 34+2*$第四章 串一、 选择题1、 串是一种特殊的线性表，其特殊性体现在( )。  A) 可以顺序存储 B) 数据元素是一个字符 C) 可以链接存储 D) 数据元素可以是多个字符2、有两个串P和Q，求P在Q中首次出现的位置的运算称( )。  A )连接 B) 模式匹配 C) 求子串 D) 求串长3、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。A）2n-1 B）n2 C）(n2/2)+(n/2) D）(n2/2)+(n/2)-1 E） (n2/2)-(n/2)-1 4、设串s1='ABC

35、DEFG',s2='PQRST',函数concat(x,y)返回x和y串的连接串，subString(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，Strlength(s)返回串s的长度，则concat(subString(s1,2,Strlength(s2),subString(s1,Strlength(s2),2)的结果串是( )。 A) BCDEF B) BCDEFG C) BCPQRST D) BCDEFEF5、顺序串中，根据空间分配方式的不同，可分为( )。  A) 直接分配和间接分配   B) 静态分配和动态分配 

36、0;C) 顺序分配和链式分配   D) 随机分配和固定分配6、设串S=”abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（ ）。A) 8 ； B) 37； C) 36； D) 9。7、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（ ）。A) O(m) ； B) O(n)； C) O(n* m)； D) O(m+n)。8、已知串S=aaab,其Next数组值为（ ）。A0123 B1123 C1231 D1211二、 填空题1、 在空串和空格串中，长度不为0的是( )。2、 空格串是指_(1)_，其长度等于_(2)_3、按存储结构不同，串可

37、分为( )、（ ）、（ ）。4、C语言中，以字符( )表示串值的终结。5、在块链串中，为了提高存储密度，应该增大( ).6、假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占( )个字节。7、串操 作虽然较多，但多可通过五种操作（ ）、（ ）、（ ）、 （ ）、（ ）构成的最小子集中的操作来实现。8、设串S=Ilikecomputer .，T=com，则Length (S ) = （ ）。Index(S,T,1) = ( )9、在KMP算法中，nextj只与（ ）串有关，而与（ ）串无关。10、模式串P=abaabcac的next函数值序列为（ ）。11、两个字符串

38、相等的充分必要条件是（ ）。12、串是一种特殊的线性表，其特殊性表现在（ ）；串的两种最基本的存储方式是（ ）。三、 问答题与算法题1、 简述下列每对术语的区别：空串和空格串：串常量和串变量：主串和子串：目标串和模式串。2、在C语言中假设有如下的串说明：char s130="Stocktom", s230="March51999", s330, ()在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); ()调用函数strcmp(s1,s2)的返回值是什么? ()调

39、用函数strcmp(s15,"Ton")的返回值是什么? ()调用函数strlen(strcat(s1,s2)的返回值是什么? 、 利用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)、利用C的库函数strlen 和strcpy(或strcpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始

40、的连续m个字符。若istrlen(S),则没有字符被删除；若i+mstrlen(S),则将S中从位置i开始直至末尾的字符均删去。void StrDelete(char *S, int i ,int m) /串删除5、若S和T是用结点大小为1的带头结点的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 Int indexst(LinkList S, linkLint T)6、在KMP算法中，求下列模式串的nextj。（1） abaabcac （2）aaabaaba7、S=abcabcaabcabcabbacb, T=abcabcabbac，画出以T为模式串，以S为目标串的KM

41、P算法匹配过程8、如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一算法，输入字符串S，以“！”作为结束标志。如果串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebccadddddaaadd!”，则输出“ddddd”。第五章 数组与广义表一、 选择题1、稀疏矩阵的一般的压缩方法有( )。  A) 二维数组 B) 广义表 C) 三元组表 D) 一维数组2、设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B中。

42、对下三角矩阵中任一元素aij (i>=j)，在一维数组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+j3、在稀疏矩阵的三元组表表示法中，每个三元组表示( )。  A) 矩阵中数据元素的行号、列号和值 B) 矩阵中非零元素的值  C) 矩阵中非零元素的行号和列号 D) 矩阵中非零元素的行号、列号和值4、对稀疏矩阵进行压缩存储是为了( )。  A) 便于进行矩阵运算 B) 便于输入和输出 C) 节约存储空间 D) 降低运算的时间复杂度5、 假设以行序为主序

43、存储二维数组A=array1.100，1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5，5=（ ）。 A） 808 B） 818 C）1010 D） 10206、 设有数组Ai,j，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5，8的存储首地址为( )。A） BA+141 B） BA+180 C） BA+222 D） BA+2257、广义表是线性表的推广，它们之间的区别在于( )。  A) 能否使用子表 B) 能否使用原子项  C) 表的长度   D) 是否能为空

44、8、已知广义表L=（x,y,z），a，（u，t，w），从L表中取出原子项t的运算是（ ）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L） D. head（tail(head（tail（tail（L）)）9、已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B),下列运算的结果是: tail(head(tail(C) =( )。A）（a） B） A C） a D） (b) E） b F） (A)10、 广义表运算式Tail(a,b),(c,d)的操作结果是（ ）。A） (c,d

45、) B） c,d C） (c,d) D） d11、广义表（a,b,c,d）的表头是（ ），表尾是（ ）。A） a B）（） C）（a,b,c,d） D）（b,c,d）12、设广义表L=（a,b,c），则L的长度和深度分别为（ ）。 A） 1和1 B） 1和3 C） 1和2 D）2和313、下面说法不正确的是( )。 A） 广义表的表头总是一个广义表 B） 广义表的表尾总是一个广义表C） 广义表难以用顺序存储结构 D） 广义表可以是一个多层次的结构14、已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是( )。 A）head(tail(LS) B）

46、tail(head(LS)C）head(tail(head(tail(LS) D) head(tail(tail(head(LS)15、设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n)二、 填空题1、n维数组中的每个元素都最多有( )个直接前趋。2、对于一个一维数组A12，若一个数据元素占用字节数为S，首地址为1，则Ai(i>=0)的存储地址为( )，若首地址为d，则Ai的存储地址为( )。3、已知二维数组Amn采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A00），则Aij的地址是( )。4、 多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种( )存取结构。5、 阵的压缩存储就是为多个相同的非零元素分配( )个存储空间，零元素不分配空间。6、递归是算法设计的重要方法，递归由（ ）项和（ ）项构成。用递归的方法求广义表LS的深度DEPTH(LS)，写出基本项和递归项。 基本项：递归项： 7、广义表( a , ( a , b ) , d