《数据结构》课后题及答案
第一章绪论
一、选择题
1、( )是数据的基本单位。
A) 数据结构B)数据元素C)数据项D)数据类型
2、以下说法不正确的是( )。
Ａ)数据结构就是数据之间的逻辑结构。
Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。
Ｃ)数据项是组成数据元素的最小标识单位。
Ｄ)数据的抽象运算不依赖具体的存储结构。
3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（）等5个特性。
A)可执行性、可移植性和可扩充性B)可行性、确定性和有穷性
C)确定性、有穷性和稳定性D)易读性、稳定性和安全性
4、一般而言，最适合描述算法的语言是( )。
A)自然语言B)计算机程序语言
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)分析算法的效率以求改进D)分析算法的易懂性和文档性
8、下面程序段的时间复杂度为（）。
for( i=0; i for( j=0; j a[i][j]=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、在线性结构中，第一个结点（）前驱结点,其余每个结点有且只有（）个前驱结点；最后一个结点（）后继结点；其余每个结点有且只有（）个后继结点。 3、在树形结构中,树根结点没有（）结点，其余每个结点有且只有（）个前驱结点；叶子结点没有（）结点，其余每个结点的后继结点可以（）。 4、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着( ) 、（）和（）的关系。 5、评价一个算法优劣的两个主要指标是（）和（）。 6、数据的逻辑结构被分为( )、( )、( )和( )四种。 7、数据的存储结构被分为( )、（）、（）、（）四种. 8、算法的时间复杂度除了与问题的规模有关外，还与输入实例的( )有关。 三、问答题与算法题 1、简述下列概念： 数据元素： 数据结构： 数据类型： 数据的逻辑结构及其4种类型： 数据的存储结构及其4种方式： 2、设两个算法在同一台机器上执行，其执行时间分别是n2和2 n，要使前者快于后者，n 至少需要多大？ 3、有时为比较两个同数量级的算法优劣，须突出主项的常数因子，而将低次项用”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 )，因为前者的系数因子小于后者。请用此方法表示下列函数，并指出当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) 数据元素；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) 连续和不连续都可以。 7、一个长度为n的线性表顺序存储，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移( ) 个元素。 A) n-i B) n-i+1 C) n-i-1 D) i 8、( )运算中，使用顺序表比链表好。 A) 插入B) 删除C) 根据序号查找 D) 根据元素值查找 9、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n) 10、在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n)时，需要从前向后依次前移( )个元素。 A) n-i B) n-i+1 C) n-i-1 D) i 11、在一个长度为n的线性表中顺序查找值为x的元素时，平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为( )。 A) n B) n/2 C) (n+1)/2 D) (n-1)/2 12、在一个带头结点的单链表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 ; 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->next; 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->Prior=q; D) q->Prior=p->Prior; q->Next=q; p->Prior=q; p->next=q; 二、填空题 1、对于一个具有n个结点的单链表，在已知结点*p的后插入一个新结点的时间复杂度为（）,在给定值为x的结点后插入一个新结点的时间复杂度为（）。 2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 （）和（）。 3、顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。 4、对于双向链表,在两个结点之间插入一个新结点需修改( )个指针，单链表为( )个。 5、循环单链表的最大优点是( ) 。 6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在( )结点的next域中。 7、带头结点的双循环链表L为空表的条件是（）。 8、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用( )存储结构。 9、求顺序表和单链表的长度算法的时间复杂度分别是( )和( )。 10、顺序表存储结构的优点是( )、( )、 ( )；缺点是( )。 11、单链表存储结构的优点是( )、( )；缺点是 ( )、( )。 12、在单链表中，设置头结点的作用是( ) 。 13、链接存储的特点是利用( )来表示数据元素之间的逻辑关系。 14、带头结点的双循环链表DL为空表的条件是：( )。 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 ] != S.a[ j ] ) { ____________ ; ______________ ; } i ++ ; } ______________ ; } 16．设双链表的结点的存储结构如下：删除链表中指针p所指结点的两步主要操作是： ( )，( )。 三、问答题与算法题 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、写出下图双链表中对换值为23和15的两个结点相互位置时修改指针的有关语句。结点结构为：(prior,data,next) 6、V oid AA(SqList &L, int i, int x) { if(i>=1&&i<=Length(L)) { FOR(j= Length (L);j>=i;j - -) A[j+1]=A[j]; A[i]=x; } else exit(ERROR); } 假定调用该算法时线性表L的内容为（15，26，37，48，55），i为3, x为51，则调用返回后该单链表的内容变为什么? 7、重写建立单连表的算法CreatList_L(Linklist &L,int n )，要求顺序输入n个元素的值(即先输入a1,a2…..). CreatList_L(LinkList &L ；int n) 8、设顺序表L是一个递减有序表，试写一算法，插入元素x，插入后仍保持L的有序性。V oid sinsert(Sqlist &S, int x) 9、写一算法，在带头结点 ．．．．的单链表上实现线性表的求表长ListLength(L)运算。 int ListLength(LinkList L) 10、写出从一个带头结点 ．．．．的单链表中删除其值等于给定值x的结点的算法函数。 Int delete(LinkList &L, int x){ 11、已知递增有序的两个带头结点 ．．．．的单链表La，Lb分别存储了一个非空集合A,B。设计算法实现求两个集合的并集的运算A=A∪B void mergelist(linklist &La, linklist Lb) 12、设计算法将不．带．表头结点 ．．．．的单向链表就地逆转。 13、删除整数数组中值相等的多余整数(只保留第一次出现的那个整数)。 Void delDuplicate(int A[]，int & n) 第三章栈和队列 一、选择题 1、对于栈，操作数据的原则是（）。 A) 先进先出B) 后进先出 C) 后进后出 D) 不分顺序 2、一般情况下，将递归算法转换成非递归应通过设置（）实现。 A) 数组；B) 线性表；C) 队列；D) 栈。 3、栈和队列的共同点是（） A) 都是先进后出B) 都是先进先出 C) 只允许在端点处插入和删除元素D) 没有共同点 4、若栈的入栈序列是abcde，则栈的不可能的输出序列是()。 A) edcba B) decba C) dceab D) abcde 5、在对栈的操作中，能改变栈的结构的是()。 A) StackLength(S) B) StackEmpty(S) C) GetTop(S) D) ClearStack(S) 6、在一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈,执行()。 A) HS->next=s; 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+1D) 不确定 8、若用一个大小为６的数组来实现循环队列，且当前尾指针rear和头指针front的值分别为０和３，当从队列中删除一个元素，再加入两个元素后，尾指针rear和头指针front的值分别是（）。 A) １和５；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,pop 10、设用一个大小m=60的顺序表A［m］表示一个循环队列，如果当前的尾指针rear=32，头指针front＝15, 则当前循环队列的元素个数是( )。 A) 42 ；B) 16 ；C) 17 ；D) 41 。 11、设用顺序表a[n]表示循环队列，头、尾指针分别为front和rear，则判断队列为空的条件是（），判断队列满的条件是（）。 （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、循环队列存储在数组A[0..m]中，则入队时的操作为（）。 A) rear=rear+1 B) rear=(rear+1) mod (m-1) C) rear=(rear+1) mod m D) rear=(rear+1) mod (m+1) 13、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区应该是一个（）结构。 A) 栈；B) 队列；C) 数组；D) 线性表。 14、设栈用向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 A．V[++top]=x ; B. V [top++]=x; C. V[--top] =x ; D. V [top--]=x; 15、若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 16. 表达式a*(b+c)-d的后缀表达式是( )。【南京理工大学 2001 一、2（1.5分）】 A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd 二、填空题 1、在栈中，可进行插入和删除操作的一端称( )。 2、在作进栈运算时,应先判别栈是否( ),在作退栈运算时应先判别栈是否( )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )。 3、栈的特点是()，队列的特点是（）。 4、由于链栈的操作只在链表头部进行，所以没有必要设置()结点。 5、带头结点的单链表L是空表的条件是（）；顺序栈S是空栈的条件是（）；顺序栈S满的条件是（）；不带头结点的链栈L是空栈的条件是（）；循环队列Q是空队列的条件是（）；循环队列Q是满队列的条件是（） 6、用数组Q（其下标在0…n-1之间，共有n个元素）表示一个循环队列，front 为当前队头元素的前一个位置，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的操作串为( )。 三、问答题与算法题 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、假设用带头结点的单循环链表表示队列 ．．．．．．．．．．．．．．，并设置一个指向尾结点的指针（无头指针），请分别写出队列的入队和出队算法。 (1)int EnQueue_L(Queueptr &QL QelemType e) (2)int DeQueue_L(Queueptr &QL QelemType &e) 4、指出下述程序段的功能是什么? (1) void abc1(Stack &S) { int i，arr[64] , n=0 ; while (! StackEmpty(S)) { Pop(S，e);arr[n++]=e}; for (i=0, i< n; i++) Push(S, arr[i]); } (2) Void abc2 (Stack S1,Stack & 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)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->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)。 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、从键盘上输入一个逆波兰表达式，用伪码写出其求值程序。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$ 第四章串 一、选择题 1、串是一种特殊的线性表，其特殊性体现在( )。 A) 可以顺序存储B) 数据元素是一个字符 C) 可以链接存储D) 数据元素可以是多个字符 2、有两个串P和Q，求P在Q中首次出现的位置的运算称()。 A ) 模式匹配B) 连接C) 求子串D) 求串长 3、设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（）。 A） n2 B）(n2/2)+(n/2) C）(n2/2)+(n/2)-1 D） (n2/2)-(n/2)-1 4、设串s1='ABCDEFG',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) BCDEFEF 5、顺序串中，根据空间分配方式的不同，可分为( )。 A) 直接分配和间接分配B) 静态分配和动态分配 C) 顺序分配和链式分配D) 随机分配和固定分配 6、设串S=”abcdefgh”，则S的所有非平凡子串（除空串和S自身的串）的个数是（）。 A) 8 ；B) 37；C) 36；D) 35。 7、设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A) O(m) ；B) O(n)；C) O(m+n)；D) O(n*m)。 8、已知串S=‘aaab’,其Next数组值为（）。 A．0123 B．1123 C．1231 D．1211 二、填空题 1、在空串和空格串中，长度不为0的是( )。 2、空格串是指( )，其长度等于( )。 3、按存储结构不同，串可分为( )、（）、（）。 4、C语言中，以字符()表示串值的终结。 5、在块链串中，为了提高存储密度，应该增大( ). 6、假设每个字符占1个字节，若结点大小为4的链串的存储密度为50%，则其每个指针占 ( )个字节。 7、串操作虽然较多，但都可通过五种操作（）、（）、（）、（）、（）构成的最小子集中的操作来实现。 8、设串S=’Ilikecomputer .’，T=’com’，则Length (S ) = （）。Index(S,T,1) = ( ) 9、在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10、字符串’ababaaab’的nextval函数值为（）。 11、两个字符串相等的充分必要条件是（）。12．实现字符串拷贝的函数 strcpy为： void strcpy(char *s , char *t) /*copy t to s*/ { while ( ________ ) ； } 三、问答题与算法题 1、简述下列每对术语的区别： 空串和空格串： 串常量和串变量： 主串和子串： 目标串和模式串。 2、在C语言中假设有如下的串说明： char s1[30]="Stocktom", s2[30]="March51999", s3[30], (１)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (２)调用函数strcmp(s1,s2)的返回值是什么? (３)调用函数strcmp(s1[5],"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) 4、利用C的库函数strlen 和strcpy(或strcpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(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算法中，求下列模式串的next[j]。 （1）‘abaabcac’（2）’aaabaaba’ 7、设目标为t=‘abcaabbabcabaacbacba ’,模式为p=‘abcabaa ’ （1）计算模式p 的naxtval 函数值； （2）不写出算法,只画出利用KMP 算法进行模式匹配时每一趟的匹配过程。 11．写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。 第五章 数组与广义表 一、 选择题 1、稀疏矩阵的一般压缩方法是( )。 A) 二维数组 B) 广义表 C) 三元组表 D) 一维数组 2、设矩阵A ??? ? ? ??=nn n n a a a a 1111是一个对称矩阵，为了节省空间，将其下三角部分按行优先 存放在一维数组B 中。对下三角矩阵中任一元素a ij (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+j 3、在稀疏矩阵的三元组表示法中，每个三元组表示( )。 A) 矩阵中数据元素的行号、列号和值 B) 矩阵中非零元素的值 C) 矩阵中非零元素的行号和列号 D) 矩阵中非零元素的行号、列号和值 4、对稀疏矩阵进行压缩存储是为了( )。 A) 便于进行矩阵运算 B) 便于输入和输出 C) 节约存储空间 D) 降低运算的时间复杂度 5、 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。 A） 808 B） 818 C）1010 D） 1020 6、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A） BA+141 B） BA+180 C） BA+222 D） BA+225 7、广义表是线性表的推广，它们之间的区别在于()。 A) 能否使用子表B) 能否使用原子项 C) 表的长度D) 是否能为空 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） ( ) B） c,d C） ((c,d)) D） d 11、广义表（（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和3 13、下面说法不正确的是( )。 A）广义表的表头总是一个广义表 B）广义表的表尾总是一个广义表 C）广义表难以用顺序存储结构 D）广义表可以是一个多层次的结构 14、已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A）head(tail(LS)) B） 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、对于一个一维数组A[12]，若一个数据元素占用字节数为S，首地址为1，则A[i](i>=0)的存储地址为( )，若首地址为d，则A[i]的存储地址为( )。 3、已知二维数组A[m][n]采用行优先顺序存储，每个元素占k个存储单元，并且第一个元素的存储地址LOC（A[0][0]），则A[i][j]的地址是( )。 4、多维数组中，数据元素的存放地址直接可通过地址计算公式计算出。因此，数组是一种 ( )存取结构。 5、矩阵的压缩存储就是为多个相同的非零元素分配( )个存储空间，零元素不分配空间。 6、递归是算法设计的重要方法，递归由（）项和（）项构成。用递归的方法求广义表LS的深度DEPTH(LS)，写出基本项和递归项。 基本项： 递归项： 7、广义表( a , ( a , b ) , d , e , ((i , j ) , k ) ) 的长度是（ ），深度是（ ）。 8、广义表((a) , (( b ) , c ) , (((d )))) 的长度是（ ），深度是（ ）。 9、设广义表S=((a , b) , ( c , d))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则 GetHeat(GetTail(S)) = ( ) ， GetTail (GetHeat (S)) =( )。 10、设广义表S=(a , b , ( c , d) , (e , (f , g )))，GetHeat(S)和GetTail(S)是取广义表的表头和表尾函数。则GetHeat(GetTail(GetHeat (GetTail(GetTail(S)))))= ( ) 11、二维数组a[4][5][6]（下标从0开始计，a 有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是( ) 。(设a[0][0][0]的地址是1000,数据以行为主方式存储) 12、设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为( ) 。 13、己知三对角矩阵A[1..9,1..9]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为 ( ) 。 14、广义表A=（（（a ，b ），（c ，d ，e ））），取出A 中的原子e 的操作是（ ）。 15、设广义表A((( ),(a,(b),c)))，则head(tail(head(tail(head(A))))=（ ）。 三、 问答题与算法题 １、给出C 语言的三维数组A[m][n][s]地址计算公式。 ２、设有三对角矩阵 A n ╳n=????? ?? ? ? ?-nn nn a a a a a a a a a 1 3332232221 12110 0000 000 ，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求： (1)用i , j 表示k 的下标变换公式。 (2)用 k 表示 i,j 的下标变换公式。 ３、设二维数组A 5╳6的每个元素占4个字节，已知Loc(a 00)=1000，A 共占多少个字节? A 的终端结点A 45的起始地位为何? 按行和按列优先存储时，A 25的起始地址分别为何? 4、已知一个稀疏矩阵如下图所示： 0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0 (1)写出它的三元组顺序存储表示； (2)给出它的行逻辑链接的顺序存储表示； (3) 5、画出下列广义表的图形表示： (1) A=((a,b),(c,d)) (2) B=(a,(b,(c,d)),(e)) 6、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。 7、画出广义表LS=(( (b , c) , d ), (a) , ((a) , ( (b , c) , d )) , e , ( ))的具有共享结构的存储表示。 8、设广义表LS=(soldier , (teacher , student) , ( worker , farmer ) )，用取表头函数GetHead ( ) 和 取表尾函数GetTail ( )分离出原子student 。 9、画出下列矩阵的十字链表 ?? ? ? ? ? ? ??260200309007 0820 10、设任意n 个整数存放于数组A(1:n)中，试编写程序，将所有正数排在所有负数前面（要求算法复杂性为0( n)）。 第六章 树和二叉树 一、选择题 1、设高度为h 的二叉树只有度为0和2的结点，则此类二叉树的结点数至少有（ B ）个，至多有（E ）个。 A) 2h ； B) 2h-1 ； C) 2h+1； D) 2 h-1； E) 2 h -1； F) 2 h +1。 2、高度为h 的完全二叉树至少有（ D ）个结点，至多有（ B ）个结点。 A) 2 h ； B) 2 h -1 ； C) 2 h +1； D) 2 h –1 。 3、具有n 个结点的满二叉树有（ ）个叶结点。 A) n/2 ； B) (n-1)/2； C) (n+1)/2； D) n/2+1。 4、一棵具有n 个叶结点的哈夫曼树，共有（ ）个结点。 A) 2n B) 2n-1 C) 2n+1 D) 2 n -1； 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 1-1 某海洋客船船长L=155m ，船宽B=，吃水d =,排水体积▽=10900m 3，中横剖面面积A M =115m 2，水线面面积A W =1980m 2，试求： （1）方形系数C B ；（2）纵向菱形系数C P ；（3）水线面系数C WP ；（4）中横剖面系数C M ；（5）垂向菱形系数C VP 。 解：（1）550.01 .7*0.18*15510900 ==???=d B L C B （2）612.0155*11510900 ==??=L A C M P （3）710.0155*0.181980 ==?=L B A C W WP （4）900.01 .7*0.18115 ==?=d B A C M M （5）775.01 .7*198010900 ==??= d A C W VP 1-3 某海洋客货轮排水体积▽=9750 m 3，主尺度比为：长宽比L/B=, 宽度吃水比B/d=，船型系数为：C M =，C P =，C VP =，试求：（1）船长L;（2）船宽B ；（3）吃水d ；（4）水线面系数C WP ；（5）方形系数C B ；（6）水线面面积A W 。 解： C B = C P* C M =*= 762.0780 .0594 .0=== VP B WP C C C d B L C B ??? = 又因为 所以：B= L== d=B/= 762.0=WP C C B = 06.187467 .6*780.09750==??= d C A VP W m 2 1-10 设一艘船的某一水线方程为：()?? ? ???-±=225.012L x B y 其中：船长L=60m ，船宽B=，利用下列各种方法计算水线面积： （1） 梯形法（10等分）； （2） 辛氏法（10等分） （3） 定积分，并以定积分计算数值为标准，求出其他两种方法的相对误差。 解：()?? ????-±=225.012L x B y 中的“+”表示左舷半宽值，“-”表示右舷半宽值。因此船首尾部对称，故可只画出左舷首部的1/4水线面进行计算。 则：?? ????-=90012.42x y ， 将左舷首部分为10等分，则l =30/10=3.0m 。 梯形法：总和∑y i =，修正值(y 0+y 10)/2=，修正后∑`= 辛氏法：面积函数总和∑= 第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结 点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系 C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理 C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 16 void Descend(int &x, int &y, int &z) { int t; if(x while(result[i].sport!=NULL) { switch(result[i].schoolname) { case 'A': score[0].totalscore+=result[i].score; if(result[i].gender==male) score[0].malescore+=result[i].score; else score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore+=result[i].score; if(result[i].gender==male) score[1].malescore+=result[i].score; else score[1].femalescore+=result[i].score; break; case 'C': score[2].totalscore+=result[i].score; if(result[i].gender==male) score[2].malescore+=result[i].score; else score[2].femalescore+=result[i].score; break; case 'D': score[3].totalscore+=result[i].score; if(result[i].gender==male) score[3].malescore+=result[i].score; else score[3].femalescore+=result[i].score; break; case 'E': score[4].totalscore+=result[i].score; if(result[i].gender==male) score[4].malescore+=result[i].score; else score[4].femalescore+=result[i].score; break; } i++; } for(s='A';s<='E';s++) { printf("School %c:\n",s); printf("Total score of male:%d\n",score[i].malescore); printf("Total score of female:%d\n",score[i].femalescore); printf("Total score of all:%d\n\n",score[i].totalscore); } } 19 Status Series(int ARRSIZE, int a[]) 第三章 部分习题解答 3-10 AB ,AC 和DE 三杆连接如图所示。杆DE 上有一插销H 套在杆AC 的导槽内。试求在水平杆DE 的一端有一铅垂力F 作用时，杆AB 所受的力。设DE BC HE DH DB AD ===,,，杆重不计。 解： 假设杆AB ，DE 长为2a 。取整体为研究对象，受力如右图所示，列平衡方程： ∑=0C M 02=?a F By 0=By F 取杆DE 为研究对象，受力如图所示，列平衡方程： ∑=0H M 0=?-?a F a F Dy F F Dy = ∑=0B M 02=?-?a F a F Dx F F Dx 2= 取杆AB 为研究对象，受力如图所示，列平衡方程： ∑=0y F 0=++By Dy Ay F F F F F Ay -=(与假设方向相反) ∑=0A M 02=?+?a F a F Bx Dx F F Bx -=(与假设方向相反) ∑=0B M 02=?-?-a F a F Dx Ax F F Ax -=(与假设方向相反) 3-12AD AC AB ,,和BC 四杆连接如图所示。在水平杆AB 上作用有铅垂向下的力F 。接触面和各铰链均为光滑的，杆重不计，试求证不论力F 的位置如何，杆AC 总是受到大小等于F 的压力。 解： 取整体为研究对象，受力如图所示，列平衡方程： ∑=0C M 0=?-?x F b F D F b x F D = F C F C y F D F Cx F Cy F Bx F By F Dx F Dy F Hy F Bx F By F Dy F Dx F Ax F Ay 取杆AB 为研究对象，受力如图所示，列平衡方程： ∑=0A M 0=?-?x F b F B F b x F B = 杆AB 为二力杆，假设其受压。取杆AB 和AD 构成的组合体为研究对象，受力如图所示，列平衡方程： ∑=0E M 02 )2(2)(=?--?+?+b F x b F b F F AC D B 解得F F AC =，命题得证。 注意：销钉A 和C 联接三个物体。 3-14两块相同的长方板由铰链C 彼此相连接，且由铰链A 及B 固定，如图所示，在每一平板内都作用一力偶矩为M 的力偶。如b a >，忽略板重，试求铰链支座A 及B 的约束力。 解： 取整体为研究对象，由于平衡条件可知该力系对任一点之矩为零，因此有： ∑=0A M 0)(=+-M M F M B A 即B F 必过A 点，同理可得A F 必过B 点。也就是A F 和 B F 是大小相等，方向相反且共线的一对力，如图所示。 取板AC 为研究对象，受力如图所示，列平衡方程： ∑=0C M 045cos 45sin 00=-?-?M b F a F A A 解得：b a M F A -=2(方向如图所示) 3-20如图所示结构由横梁BC AB ,和三根支承杆组成，载荷及尺寸如图所示。试求A 处的约束力及杆1，2，3所受的力。 解： 支撑杆1，2，3为二力杆，假设各杆均受压。选梁BC 为研究对象，受力如图所示。其中均布载荷可以向梁的中点简化为一个集中力，大小为2qa ，作用在BC 杆中点。列平衡方程： F ABx F ABy F B F Ex F Ey F AC F B F A F B F Cx F Cy F Bx F By F 3 判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（√） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上是没有区别的，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构。（√） 7.数据的存储结构是数据的逻辑结构的存储映像。（×） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和的描述步骤。（√） 填空题： 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有 1 个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面 的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系的 有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算和事后统计法。 16.一个算法的时间复杂性是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题 规模n的函数。 18.若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O （nlog2n ）。 若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 ___O（n*n）_______ 。 数据结构是一门研究非数值计算的程序设计总是中计算机的操作对象，以及它们之间的关系和运算的学科。 19.串的两种最基本的存储方式是顺序存储方式链式存储方式。 20.两个串相等的充分必要条件是、长度相等对应位置的字符相同。 第一章绪论 一、填空题 1．数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。____数据元素_____是数据的基本单位；____数据项_______是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为____结构____。 2．数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_____数据元素的有限集____的集合D和D上____关系的有限集_____的集合R所构成的二元组：DS=（D，R）。 3． 4．一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无关时，则表示为____O(1)______；成正比关系时，则表示为_____O(n)______；成对数关系时，则表示为 ____O(log2n)_______；成平方关系时，则表示为____O(n2)______。 5．数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括____顺序________和______链式______两种类型。 6．线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有__一_____个前驱结点；最后一个结点__无_____后继结点，其余每个结点有且仅有___一____个后继结点。 7．树型结构的特点是：根结点没有__前驱______结点，其余每个结点有且仅有_____一个___个前驱结点；叶子结点_____无____后继结点，其余结点可以有___任意______个后继结点。 8．图型结构的特点是：每个结点可以有____任意_____个前驱结点和后继结点。 9．程序段for（i=1，s=0；s Exercise Statics of the Ship 响砂山月牙泉 第一章复习思考题 1．船舶静力学研究哪些容？ 2．在船舶静力学计算中，坐标系统是怎样选取的？3．作图说明船体的主尺度是怎样定义的？其尺度比的 主要物理意义如何？ 4．作图说明船形系数是怎样定义的？其物理意义如 何？试举一例说明其间的关系。 5．对船体近似计算方法有何要求？试说明船舶静力学 计算中常用的近似计算法有哪几种？其基本原理、适用围以及它们的优缺点。 复习思考题 6．提高数值积分精确度的办法有哪些？并作图说明梯 形法、辛浦生法对曲线端点曲率变化较大时如何处理？以求面积为例，写出其数值积分公式。 7．分别写出按梯形法，辛浦拉法计算水线面面积的积 分公式，以及它们的数值积分公式和表格计算方法。(5,8,-1) 法、(3,10,-1)法的适用围。 8．写出计算水线面面积的漂心位置和水线面面积对x 轴y轴的惯性矩的积分公式。并应用求面积的原理写出其数值积分公式和表格计算方法。 复习思考题 9．如何应用乞贝雪夫法？试以九个乞贝雪夫坐标，写出求船舶排水体积的具体步骤。 10．说明积分曲线、重积分曲线与原曲线的关系．并以水线面面积曲线为例说明积分曲线、重积分曲线的应用。Exercise 1-1 已知: L=155m,B=18m,d=7.1m,V=10900m 3 ,Am=115m 2 , Aw=1980m 2 求：Cb=V/LBd=10900/(155*18*7.1)=0.550 Cp=V/Lam=10900/(155*115)=0.62 Cw=Aw/BL=19800/(18*155)=0.710 Cm=Am/Bd=115/(18*7.1)=0.900 Cvp=V/Awd=10900/(1980*7.1)=0.775 某海洋客船L=155m，B=18m，d=7.1m，V=10900m3，Am=115m 2 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 第一章绪论 1．下面是几种数据的逻辑结构S=(D，R)，分别画出对应的数据逻辑结构，并指出它们分别属于何种结构。 D={a，b，c，d，e，f} R={r} (a) r={ 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 数据结构题集答案 数据结构题集 第一章绪论 一、单选题 1.在数据结构中，从逻辑上可以把数据结构分成【 C 】。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指【 A 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 D.数据元素之间的关系 3. 【 A 】是数据的最小单位，【 B 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 4. 计算机所处理数据一般具有某种内在联系，这是指【 B 】。 A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系 C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系 5.算法分析的目的是【 C 】。 A.找出数据结构的合理性 B.研究输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性 6.在存储数据时，不仅要考虑存储各数据元素的值，而且还要存储【 C 】。 A.数据处理的方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 7.算法分析的主要任务是分析【 D 】。 A.算法是否具有较好的可读性 B.算法中是否存储语法错误和逻辑错误 C.算法的功能是否符合设计要求 D.算法的执行时间与问题规模之间的关系。 8.数据的运算【 A 】。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 9.算法的计算量的大小称为算法的【 B 】。 A.效率 B.时间复杂度 C.现实性 D.难度 10.连续存储分配时，存储单元的地址【A 】。 A.一定连续 B.一定不连续 C.不一定连续 D.部分连续，部分不连续 二、判断题 1.数据元素是数据结构的最小单位【.×】。 2.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构【×.】。 3.数据的逻辑结构指数据元素的各数据项之间的逻辑关系【×.】。 4.算法的优劣与算法的描述语言无关，但与使用的计算机有关【.×】。 5.数据结构的抽象操作的定义与具体实现有关【.×】。 第三章 初稳性 习题解 3-3 某巡洋舰的排水量△=10200t ，船长L=200m ，当尾倾为1.3m 时，水线面面积的纵向惯性矩I L =420*104m 4，重心的纵向坐标x G =-4.23m ，浮心的纵向坐标x B =-4.25m ，水的重量密度3/025.1m t =ω。 3-13 某船长L=100m ，首吃水d F =4.2m ，尾吃水d A =4.8m ，每厘米吃水吨数TPC=80t/cm ，每厘米纵倾力矩MTC=75tm ，漂心纵向坐标x F =4.0m 。今在船上装载120t 的货物。问货物装在何处才能使船的首吃水和尾吃水相等。 解：按题意要求最终的首尾吃水应相等，即'='A F d d 设货物应装在(x,y,z)处，则装货后首尾吃水应满足： A A F F d d d d d d δδδδ++=++，即A A F F d d d d δδ+=+ （1） ??? ??????? ??+-=??? ??-=θδθδtg x L d tg x L d F A F F 22 （2） () L F GM x x P tg ??-=θ （3） L GM MTC L 100??= M T C L GM L ?=??∴100 （4） 将式（2）、（3）、（4）代入式（1）中得： ()()MTC L x x P x L d MTC L x x P x L d F F A F F F ?-??? ??+-=?-??? ??-+10021002 代入数值得： ()()75*100*1000.4*1200.420.1008.475*100*1000.4*1200.420.1002.4-?? ? ??+-=-??? ??-+x x 解得： x=41.5m 答：应将货物放在（41.5，0，z ）处。 3-14 已知某长方形船的船长L=100m ，船宽B=12m ，吃水d =6m ，重心垂向坐标z G =3.6m ，该船的中纵剖面两边各有一淡水舱，其尺度为：长l =10m ，宽b=6m ，深a=4m 。在初始状态两舱都装满了淡水。试求：（1）在一个舱内的水耗去一半时船的横倾角； （2）如果消去横倾，那们船上x=8m ，y=-4m 处的60t 货物应移至何处？ 解： 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构试题 一、单项选择 1、若某线性表中最常用的操作是在最后一个元素之后插入和删除元素，则采用___________最节省运算时间. A、单链表 B、仅有头指针的单循环链表 C、仅有尾指针的单循环链表 D、双链表 2、哈夫曼树的带权路径长度WPL等于___________. A、除根以外的所有结点的权植之和 B、所有结点权值之和 C、各叶子结点的带权路径长度之和 D、根结点的值 3、设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是___________. A、1,2,3,4,5 B、1,4,3,2,5 C、4,1,3,2,5 D、1,3,2,5,4 4、20个结点的完全二叉树，其高度为___________. A、3 B、2 C、4 D、5 5、栈和队列都是___________. A、顺序存储的线性结构 B、链式存储的线性结构 C、限制存储点的线性结构 D、限制存储点的非线性结构 6、已知完全二叉树有30个结点，则整个二叉树有___________个度为1的结点. A、0 B、1 C、2 D、不确定 7、对于N个结点的完全无向图，其边数是___________ A、N B、N2 C、N(N-1)/2 D、N(N-1) 8、队列的特点是 A、先进先出 B、先进后出 C、后进先出 D、不进不出 9、连通分量是的极大连通子图。 A、有向图 B、树 C、无向图 D、图 10、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为.............................. A、向量 B、树 C、图 D、二叉树 11、栈和队列都是（）. A、线性结构 B、链式存储的线性结构 C、线性结构或非线性结构 D、非线性结构 12、二叉树第J层有（）个结点 A、J B、2J C、J+1 D、不能确定 13、若图G中（）是有向的，则称此图为有向图. 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 《数据结构》试卷及答案 1．算法分析的目的是( )。 A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是( )。 A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D) 5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( )。 A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front 6．设有串t='I am a good student '，那么Substr(t,6,6)=（）。 A. student B. a good s C. good D. a good 7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为（）。 A.23 B.33 C.18 D. 40 8．已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（）。 A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS)) 9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( ) A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( ) 不是树的存储形式。 A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法 11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是( )。 A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（），且限于（）。数据结构试题及答案(免费)
船舶静力学作业题答案
数据结构习题解答
数据结构题集c语言版答案严蔚敏吴伟民[1]
静力学第三章习题答案
数据结构题集与答案
数据结构习题集
船舶静力学课后习题答案
数据结构习题与答案
数据结构习题集(积分)
数据结构试题(含答案)
数据结构题集答案复习过程
船舶静力学第三章习题答案
数据结构习题集答案解析_清华大学版
数据结构习题集
数据结构试题及答案
严蔚敏数据结构题集(C语言版)完整答案.doc
数据结构试卷及答案压缩版