下载文档原格式
第一次作业------------线性表题目1、下列图1单链表执行R->data=P->next->data语句后，P->next->data值为A. 5B. 7C. 2D. 3题目2、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。
A. 向量大小B. 基地址和结点大小C. 结点大小D. 基地址题目3、非空的循环单链表head的尾节点（由r所指向）满足 ( )A. r->next=NULLB. r->next=headC. r=NULLD. r=head题目4、设线性表（a1,a2,a3···an）按顺序存储,且每个元素占有m个存储单元，则元素ai 的地址为A. LOC(a1) + i×m ，其中LOC(a1)表示元素a1的地址B. 元素ai的地址无法计算C. LOC(a1) + (i-1)×m，D. LOC(a1) + (i－2)×m题目5、在（）运算中，使用顺序表比链表好。
A. 根据元素值查找B. 插入C. 根据序号查找D. 删除题目6、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点A. P→next=S;S→next=PB. S→next=P→next; P=SC. S→next=P→next;P→next=SD. S→next=P;P→next=S题目7、在双向循环链表的*p结点之后插入*s结点的操作是A. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;B. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;C. p->next=s; s->prior=p; p->next->prior=s; s->next=p->nextD. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next题目8、单链表表示的整数数列如下图，值P->next->next->data为:A. 47B. 93C. 19D. 64题目9、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。
假设有两个按元素值递增次序排列的线性表,均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递增次序排列的单链表。
【解答】算法的基本设计思想:因为两链表已按元素值递增次序排列,将其合并是,均从第一个结点起进行比较,将小的结点链入链表中,同时后移链表工作指针。
该问题要求结果链表按元素值递减次序排列,故新链表的建立,应该采用头插法(也就是书本上讲的那种从链表中插入元素值的方法。
比较结束后,可能会有一个链非空,此时用头插法将剩下的结点依次插入新链表中即可。
算法实现如下: void MergeList(ListList &La,LinkList &Lb {LinkList r,pa=La->next,pb=Lb->next; //pa和pb分别是链表La 和//Lb的工作指针La->next=NULL;while(pa&&pb //当两链表均不为空时if(pa->data<=pb->data {r=pa->next; //将pa的后继结点暂存于rpa->next=La->next;La->next=pa; //将pa结点链于结果表中,同时逆//置(头插法pa=r; //恢复pa为当前待比较结点}else {r=pb->next; //将pb的后继结点暂存于rpb->next=La->next;La->next=pb; //将pb结点链于结果表中,同时逆置pb=r;}If(pa pb=pa; //通常情况下会剩下一个链表非空,处理剩//下的部分while(pb{r=pb->next;pb->next=La->next;La->next=pb;pb=r;}free(Lb;}选择题:1、D 2、B1、栈的特点是先进后出,由于进栈和出栈操作是可以穿插着进行的。
当第i个元素第一个出栈时,则i之前的元素可以依次排在i之后出栈,但剩余的元素可以在此时进栈并且也会排在i之前的元素出栈,所以第就j个出栈的元素是不确定的。
武汉大学计算机学院2011年－2012学年第一学期“数据结构”考试试题（A）要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。
每张答题纸都要写上姓名和学号。
一、单项选择题（共20小题，每小题2分，共40分）1. 下列各选项中属于逻辑结构的是。
A.哈希表B.有序表C.单链表D.顺序表2. 对于数据结构，以下叙述中不正确的是。
A.数据的逻辑结构与数据元素本身的形式和内容无关B.数据的逻辑结构是数据的各数据项之间的逻辑关系C.数据元素是数据的基本单位D.数据项是数据的最小单位3. 某算法的时间复杂度为O(n2)，表明该算法的。
A.问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比4. 通常在单链表中增加一个头节点，其目的是为了。
A.使单链表至少有一个节点B.标识表节点中首节点的位置C.方便单链表运算的实现D.说明单链表是线性表的链式存储5. 删除某个双链表中的一个节点（非首、尾节点），需要修改个指针域。
A.1B.2C.3D.46. 栈和队列是两种不同的数据结构，但它们中的元素具有相同的。
A.抽象数据类型B.逻辑结构C.存储结构D.运算7. 元素a、b、c、d、e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的序列个数是。
A.3B.4C.5D.68. 设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为。
A.r-fB.r-f-1C.(r-f)％N+1D.(r-f+N)％N9. 已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。
若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是。
A.0，0B.0，n-1C.n-1，0D.n-1，n-110. 对于n阶（n≥2）对称矩阵，采用压缩方法以行序优先存放到内存中，则需要个存储单元。
数据结构第一次作业数据结构第一次作业一．单项选择题(20分)( )1.已知一算术表达式的后缀形式为ABC *+DE-/，则其中缀形式为 _________。
a、(A＋B *C)/(D-E)b、A+B*C /D-Ec、(A+B*C)/D-Ed、A+B*C/(D-E)( )2.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用________存储方式最节省运算时间（假设链表仅设有一个first指针）。
a. 单链表b. 带头结点的双循环链表c. 单循环链表d. 双链表( )3.设一个栈的输入序列为A，B，C，D，则所得到的输出序列不可能是_______。
a. A，B，C，Db. D，C，B，Ac. A，C，D，Bd. D，A，B，C( )4.若线性表最常用的操作是存取第i个元素及其直接前驱的值，则采用_____存储方式节省时间。
a．顺序表 b．双链表 c．单循环链表 d．单链表( )5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为_______。
(1≤i≤n+1)a、O(0)b、O(1)c、O(n)d、O(n2)( )6.若指针L指向一带头结点的循环单链表的头结点，该表为空表的条件是_______为真值；a. !( L -> link );b. L == (L -> link) -> link;c. L -> link;d. L == L -> link;( )7.用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是________：a. front = (front + 1) mod N;b. front = (front - 2)mod N;c. front = front + 1;d. front = front – 2;( )8.若用Head()和Tail()分别表示取广义表的表头和表尾，广义表A=（1,2,(3,4),(5,(6,7))），则Head(Tail(Head(Tail(Tail(A))))) 。
《数据结构》（01111、01211）作业题（一）一、判断题（下列各题，你认为正确的，请在前面的括号内打√，错误的打×。
每题1分，共10分）1、（√）2、（√）3、（√）4、（√）5、（√）6、（╳）7、（√）8、（√）9、（╳）10、（√）（√）1. 数据的存贮结构是数据的逻辑结构的存贮映象。
（√）2. 用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。
（√）3. 非线性结构中，至少存在一个元素不止一个直接前趋或不止一个直接后继。
（√）4. 树的最大特点是层次结构。
（√）5. 队列的特点是先进先出。
（╳）6. 图的最小生成树是唯一的。
（√）7. 线性表是广义表的特殊形式。
（√）8. 后序序列和中序序列能唯一确定一棵二叉树。
（╳）9. 散列表是一种链式存贮结构。
（√）10. 快速排序并非在任何情况下都比其它排序方法速度快。
二、填空题（每空2分，共20分）1．数据的存贮结构的四种形式为存贮、存贮、存贮和存贮。
2．所有插入和删除都在表的一端进行的线性表称为。
3．n个结点的完全二叉树，其深度h= 。
4．对于顺序循环队列Q[M]，下标从0到M-1，头尾指针分别为F和R，入队时，队尾指针循环加1可表示为R= 。
5．散列法既是一种查找方法，又是一种方法。
6．n个顶点的有向完全图具有条弧。
7．n个元素的顺序查找的平均查找长度为。
三、单选题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共15分）。
1．若进栈序列为1，2，3，4，则不可能得到的出栈序列是（）（1）3,2,1,4 （2）3,2,4,1 （3）4,2,3,1 （4） 2,3,4,12．对于下列二叉树，其后序序列为（）（1）ABDECFG （2）DBEAFCG （3）DEBFGCA （4）GFCEBDA3．对于下列AOV网，不能出现的拓扑序列为（）（1）1 2 3 4 5 （2）1 2 4 3 5 （3）2 4 1 3 5 （4）2 1 4 3 5AB C DEFG题三2图13542题三、3图4．深度为k 的完全二叉树所含叶结点的个数最多为 （ ） （1）2k （2） 2k-1 （3） k （4） 2k 5．衡量查找算法效率的主要标准是 （ ） （1） 元素个数 （2） 所需的存贮量 （3） 平均查找长度 （4） 算法难易程度 四、应用题（25分）1．将下列森林转化为二叉树。
1、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。
A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]2、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。
A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;3、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。
A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法4、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。
A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法5、队列的操作的原则是（ A ）。
A）先进先出 B) 后进先出C) 只能进行插入 D) 只能进行删除6、n个顶点的图的最小生成树必定（ D ），是不正确的描述。
A）不唯一 B）权的总和唯一C）不含回路 D）有n条边7、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（ D ）。
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;8、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。
B）线性表采用链接存储，便于插入和删除操作。
C）线性表采用链接存储，不必占用一片连续的存储单元。
数据结构第一次作业一、单选题 (共100.00分)1. 已知栈S为空，数据1、2、3、4依次逐个进入栈S，则栈顶数据为（）A. 1B. 2C. 3D. 4正确答案：D2. 栈的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：B3. 队列的最大特点是（）A. 先进先出B. 后进先出C. 无限递归D. 有限递归正确答案：A4. 已知栈包含10元素，其中存放在栈底是第1号元素，则第10号元素可以通过（）进行访问A. 栈底B. 栈中C. 栈尾D. 栈顶正确答案：D5. 以下结构中，哪一个是属于物理结构（）A. 栈B. 队列C. 链队列D. 线性表正确答案：C6. 使用长度为10的数组实现循环队列，则该队列最多存储数据个数为（）A. 1B. 9C. 11.D.5正确答案：B7. 已知顺序表包含1000个数据，现在第88号位置插入新的数据，需要移动的数据个数为（）A. 88B. 87C. 912D. 913正确答案：D8. 若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是（）A. 单链表B. 双链表C. 单循环链表D. 顺序表正确答案：D9. 以下结构中，哪一个是属于物理结构（）A. 线性表B. 栈C. 单链表D. 队列正确答案：C10. 已知顺序表包含100个数据，现在要删除第99号位置的数据，需要移动的数据个数为（）A. 99B. 100C. 1D. 2正确答案：C已知指针p指向单链表L的某个结点，判断p指向的结点是尾结点的条件是（）A. if (p->next>p)B. if (p->next==NULL)D. if (p->data==0)正确答案：B12. 以下描述哪个是正确的（）A. 线性表的数据元素的存储位置一定是连续的B. 顺序表的数据元素的存储位置一定是连续的C. 链表的数据元素的存储位置一定不是连续的D. 线性表的数据元素的存储位置一定不是连续的正确答案：B已知顺序表包含100个数据，先在第15号位置插入1个新数据，接着删除第3号位置的数据，需要移动的数据总个数为（）A. 18B. 84C. 184D. 188正确答案：C在数据结构概念中，数据的基本单位是（）A. 数据段B. 数据项C. 数据表D. 数据元素D在数据结构概念中，结构是描述（）A. 数据项的类型B. 数据元素之间的关系C. 数据成员的先后顺序D. 数据对象的取值范围正确答案：B在算法设计中，要求算法便于理解和修改是属于算法要求的（）A. 正确性B. 可读性C. 健壮性D. 效率高正确答案：B以下关于算法的描述，哪个是正确的（）A. 算法可以没有输入B. 算法可以包含无限个执行步骤C. 算法可以没有输出D. 算法的每个步骤允许带有歧义的正确答案：抽象数据类型ADT通过三方面描述，包括数据关系、数据操作和（）A. 数据对象B. 数据来源C. 数据范围D. 数据判断正确答案：A设n为问题规模，以下程序的时间复杂度为（）for (i=1; i<=10000; i++) for (j=1; j<=n; j++) a = a + 1;A. O(1)B. O(n)C. O(10000n)D. O(n2)正确答案：B20.设n为问题规模，以下程序的时间复杂度为（） for (i=1; i< POW（2, n）; i++) //POW(x, y)函数表示x的y次幂a = a+100;A. O(n)B. O(2n)C. O(n!)D. O(2n)正确答案：D。
《数据结构》课程第1次过程考试学号：________________ 姓名：________________ 成绩：________________一、选择题（共30分。
每小题3分。
）( A )01、算法分析的两个主要方面是__。
A)空间复杂性和时间复杂性 B)正确性和简明性 C)可读性和文档性 D)数据复杂性和程序复杂性( D )02、线性表的常用操作是存取第i个元素及其前趋的值，则采用__存储方式最省时间。
A)单向链表 B)双向链表 C)单向循环链表 D)顺序表( A )03、链表不具有的特点是__。
A)可随机访问任一元素 B)插入删除操作不需要移动元素C)不必事先估算存储空间 D)所需空间与线性表长度成正比( A )04、在单循环链表中指针p指向结点A，若要删除A之后的结点(存在)，则其中指针的链接操作为__。
A)p->next=p->next->next B)p=p->next C)p=p->next->next D)next=p( D )05、在有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较__个结点。
A)n B)n/2 C)(n-1)/2 D)(n+1)/2( B )06、对n个元素进行冒泡排序，其算法的时间复杂度为__。
A) O(n) B) O(n2) C) O(1) D) O(2n)( B )07、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是__。
A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2( C )08、如果以链表作为栈的存储结构，则退栈操作时必须判别__。
A)栈是否为满 B)栈的元素类型 C)是否为空 D)不作任何判别( D )09、数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为__。
(1)一个算法应该是（）。
A)程序B) 问题求解步骤的描述C) 要满足五个基本属性D) A 和C(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)下列程序的时间复杂度为（）。
i=0；s=0；while（s<n）{ i++；s=s+i；}2nA)O （）B) O（）C) O（n）D) O（n2）(8)下列程序段的渐进时间复杂度为（）。
for( int i=1;i<=n;i++)for( int j=1;j<= m; j++)A[i][j] = i*j ;A）O(m2) B）O(n2) C）O(m*n) D）(m+n) (9)程序段如下：sum=0；for(i=1;i<=n;i++)for(j=1;j<=n;j++)sum++；其中n 为正整数，则最后一行的语句频度在最坏情况下是（）。
2 A ）O(n ） B) O(nlogn) C) O(n 3)D) O(n 2)(10) 在下面的程序段中，对 x 的赋值语句的频度为（）for( i=1;i<=n ; i++) for ( j=1;j<=n ; j++)x:=x+1;A) O(2n)B)O(n) C) O(n 2) D) O(log n)(11) 程序段 for ( i:=n-1; i>=1; i--）for ( j:=1;j<=i ; j++)if (a[j]>a[j+1]){ t=a[j]; a[j]= a[j+1]; a[j+1]= t; }其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ ）。
