[数据结构]2010数据结构期中考试（c++）

柔光的暖阳◎ 2022-07-12 07:48 298阅读 0赞

**2010****期中考试（****c++****）**

**一、****选择题（****20****分）**

**1.****数据结构的讨论中把数据结构从逻辑结构上分为（****C** **）。**

**A.****内部结构与外部结构****B.****静态结构与动态结构**

**C.****线性结构和非线性结构****D.****紧凑结构和非紧凑结构**

**2.****算法具备输入、输出和****( C)5****个特性。**

**A.****易读性、稳定性和安全性****B.****可行性、可移植性和可扩充性**

**C.****确定性、有穷性和稳定性****D.****可行性、确定性和有穷性**

**3.****算法分析的目的是****( A )****。**

**A.****分析算法的效率以求改进****B.****研究算法中的输入和输出之间的关系**

**C.****分析算法的易懂性和文档性****D.****找出数据结构的合理性**

**4.****将下列复杂度由大到小重新排序：****(C)****A) 2n B) n! C) n5 D) 10 000 E) n\*log2n**

**A.BCAEDB.CABEDC.BACEDD.ABCED**

**\#include <iostream>**

**using namespace std;**

**void main()**

**\{**

**double n;**

**double a=1,b=1,c=1;**

**for( n=5;n<50;n+=5)**

**\{**

**for(double i=1;i<=n;i++)**

**\{**

**a=2\*a;**

**\}**

**for( i=1;i<=5;i++)**

**\{**

**b=b\*n;**

**\}**

**for( i=1;i<=n;i++)**

**\{**

**c=c\*i;**

**\}**

**cout<<"n="<<n<<" 2^n="<<a<<"n^5="<<b<<" n!="<<c<<endl;**

**\}**

**5.****下列程序片段的时间复杂度为（****C** **）。**

**x=0;**

**for(i=1;i<n;i++)**

**for(j=1;j<n;j++)**

**x++;**

**A.O(1)B.O(n)C.O(n2)D.O(n3)**

**6.****在顺序表中，数据元素的逻辑位置和物理位置的关系是（****A** **）。**

**A.****一致的****B.****不一致的****C.****大致相同****D.****个别情形相同**

**7.****在长度为****n****的顺序存储的线性表中，向第****i****个元素（****0≤i≤n****）之前插入一个新元素时，需要从后向前依次后移（****A** **）个元素。**

**A.n-iB.n-i+1C.n-i-1D.1**

**8.****线性表采用链表存储时其存储地址（****D** **）。**

**A.****必须是连续的****B.****部分地址必须是连续的**

**C.****一定是不连续的****D.****连续不连续都可以**

**9.****单链表的存储空间利用率（** **A** **）。**

**A.****小于****1B.****等于****1C.****大于****1D.****不确定**

**10.****带头结点的单链表为空的判断条件是（** **C** **）。**

**A.head==NULLB.head!=NULL**

**C.head->next==NULLD.head->data==NULL;**

**11.****在一个单链表中，若删除****p****所指结点的后继结点，则执行（****A** **）。**

**A.p->next=p->next->nextB.p=p->next;p->next=p->next->next;**

**C.p->next=p->next;D.p=p->next->next;**

**12.****从具有****n****个结点的单链表中查找其值等于****x****的结点时，在查找成功的情况下，需平均比较（** **D** **）个结点。**

**A.nB.****（****n-1****）****/2C.nD.(n+1)/2**

**13.****串的长度是（** **D** **）。**

**A.****串中不同字符的个数****B.****串中字符的个数，包括****’/0’**

**C.****串中字符的个数且大于****0D.****串中字符的个数，不包括****’/0’**

**14.****一个栈的入栈序列为****a,b,c,d,****则栈的不可能的输出序列为（** **A** **）。**

**A.dcabB.cdbaC.abcdD.dcba**

**15.****判断一个顺序栈为满的条件是（** **C** **）。**

**A.top==0B.top!=0C.top==size-1D.top!=size-1**

**16.****栈和队列的共同特点是（** **C** **）。**

**A.****都是先进先出****B.****都是后进先出**

**C.****只允许在表的端点出进行插入和删除****D.****没有共同特点**

**17.****存取数据采用先进先出原则的是（** **D** **）。**

**A.****线性表****B.****字符串****C.****栈****D.****队列**

**18.****存放顺序循环队列的数组最大容量为****size****个元素****,****该队列为满队列的条件是（****C** **）。**

**A.front==rearB.front!=rear**

**C.front==(rear+1)%sizeD.front!=(rear+1)%size**

**19.****在一个顺序循环队列中，****front****指向队首元素的（****C** **）位置**

**A.****后一个****B.****前一个****C.****当前****D.****不定**

**20.** **在一个链队列中，假定****front****和****rear****分别为头指针和尾指针，则插入一个指针****s****所指结点的操作是（****A** **）。**

**A.rear->next=s;rear=sB.front=front->next**

**C.s->next=rear;rear=sD.s->next=front;front=s**

**二、****填空题（****20****分）**

**1.****数据的逻辑结构是从逻辑关系上描述数据，它与数据的****\_****存储结构****\_****无关，是独立于计算机的。**

**2.****对于一个长度为****n****的顺序表，在表头插入元素的时间复杂度为****\_\_O(n)\_\_****，在表尾插入元素的时间复杂度为****\_ O(1)\_****。**

**3.****在一个带头结点的单循环链表中，****rear****指向尾结点，则指向头结点的指针****head****可用****rear****表示为****head****＝****\_rear->next->next\_****。**

**4.****在一个不带头结点的单链表中，若要向表头插入一个由指针****p****所指的结点，则应执行语句：****\_\_p->next = head\_\_;\_\_head = p\_\_****;**

**5.****在一个顺序栈中，栈顶指针指向栈顶元素的****\_\_****当前****\_\_****位置。**

**6.****若在双向链表中指针****p****所指的****结点之后插入一个指针****q****所指的****结点，其操作步骤为：**

**q->next=p->next;if(p->next) p->next->prov=q;**

**\_q->prov=p\_\_\_\_;\_p->next =q\_\_\_****;**

**7.****设有一个顺序栈****S****，元素****S1,S2,S3,S4,S5,S6****依次进栈，如果****6****个元素的出栈顺序为****S2,S3,S4,S6,S5,S1,****则顺序栈的容量至少应为****\_\_\_\_\_\_3\_\_\_\_\_\_\_\_\_\_****。**

**三、****判断题（****10****分）**

**1.****链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。****（****F** **）**

**2.****当栈中元素为****n****个，作进栈元素时发生上溢，则说明该栈的最大容量为****n****。（****T** **）**

**3.****用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。（****T** **）**

**4.****栈和队列都是运算受限的线性表。****（****T** **）**

**5.****做进栈运算时应先判别栈是否为空。****（****F** **）**

**6.****线性表采用顺序存储表示时，必须占用一片连续的存储单元。****（****T** **）**

**7.****已知指针****p****指向链表中的某结点，执行语句****p=p->next****不会删除该链表中的结点。**

**（****F** **）**

**8.****设一数列的顺序为****1,2,3,4,5,6,****通过栈结构可以排成的顺序是****3,2,5,6,4,1****。（****T** **）**

**9.****链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，通常存储器中还有空闲存储空间，就不会产生溢出的问题。****（****T** **）**

**10.****设有一个空栈，现有输入序列****1,2,3,4,5****，经过****PUSH,PUSH,POP,PUSH,POP,PUSH,**

**PUSH****后，输出序列为****2,1****。****（****F** **）**

### 四、程序填空题(20分) ###

**1.****下面是在顺序表第****i****（****0≤i≤n****）个元素前插入新元素****x****的算法，请在空格处填上适当的语句。**

**template <class T>**

**class SeqList**

**\{**

**private:**

**T \*element;//****动态数组存储顺序表元素**

**int size;//****顺序表的数组容量**

**int len;//****顺序表长度**

**public:**

**void insert(int i, T x)**

**\{ //****在顺序表第****i****（****0≤i≤n****）个元素前插入新元素****x**

**int j;**

**if( len == size )**

**\{ T \*temp=element;**

**element = new T\[size\*2\];**

**for(j=0;j<size;j++)**

**\_\_\_\_\_\_\_\_( 1 )\_\_\_\_\_\_\_\_; &&element\[j\] = temp\[j\];**

**size\*=2;**

**\}**

**if(i<0) i=0;**

**if(i>len) i=len;**

**for(j=len-1; j>=i;j--)**

**\_\_\_\_\_\_\_\_( 2 )\_\_\_\_\_\_\_\_; && element\[j+1\] = element\[j\];**

**\_****\_\_\_\_\_\_\_( 3 )\_\_\_\_\_\_\_\_; && element\[i\] = x;**

**\_****\_\_\_\_\_\_\_( 4 )\_\_\_\_\_\_\_\_; && len++;**

**\}**

**2.** **下面的算法是在带有头结点的单链表中，将值为****x****的新结点插入在值为****y****的结点之前。若****y****不存在，则将值为****x****的新结点插入到表尾。请在空格处填上适当的语句。**

**template <class T>**

**class Node**

**\{ public:**

**T data;**

**Node<T> \*next;**

**Node()**

**\{**

**this->next = NULL;**

**\}**

**Node(T data, Node<T> \*next = NULL)**

**\{**

**this->data=data;**

**this->next-next;**

**\}**

**\} ;**

**template <class T>**

**class SinglyLinkedList**

**\{**

**public:**

**Node<T> \*head;**

**void insert( T x, T y )**

**\{ //****在带有头结点的单链表中，将值为****x****的新结点插入在值为****y****的结点之前。**

**//****若****y****不存在，则将值为****x****的新结点插入到表尾**

**Node<T> \*q, \*p, \*r;**

**r=new Node<T>(x,NULL);**

**if ( head->next=NULL)**

**head->next=r;**

**else**

**\{ q=head;**

**p=q->next;**

**while (p!=NULL)**

**\{ if(p->data!=y)**

**\{ (1);(2); && q=p; p=p->next;**

**\}**

**else**

**(3); && break;**

**\}**

**if (p!=NULL)**

**\{ (4);(5); && r->next=p; q->next=r;**

**\}**

**else**

**(6); && q->next=r;**

**\}**

**\}//****算法结束**

### 五、程序阅读题（10分） ###

**1.****说明****function****的具体功能。**

**\#inlcude <string.h>**

**class SString**

**\{ private:**

**char \*element;**

**int size;**

**int len;**

**public:**

**void function(char \*str)**

**\{ int i,j,n=strlen(str);**

**char \*p=element;**

**if (len+n >= size )**

**\{ size=(len+n+1)\*2;**

**element=new char\[size\];**

**for(j=0;j<len;j++)**

**element\[j\]=p\[j\];**

**\}**

**else**

**\{ for (i=0;i<n;i++)**

**element\[len+i\]=str\[i\];**

**len+=n;**

**\}**

**\} //function****将****str****串联接到当前顺序串的后面**

**\}**

**2.** **说明****function****的具体功能。**

**\#include “Node.h”**

**template <class T>**

**class LinkedQueue**

**\{**

**private:**

**Node<T> \*front,\*rear;**

**public:**

**T function()**

**\{**

**PNode p;**

**if ( front!=rear )**

**\{**

**Node<T> \*p=front->next;**

**T x=p->data;**

**front->next=p->next;**

**if ( p->next==NULL )rear=front;**

**delete p;**

**return x;**

**\}**

**throw “****出错了！****”****；**

**\}//function****带头结点的链队列出队并返回队头元素。**

**\}**

**六、综合题（****20****分）**

**1.** **编写算法，在顺序表中，查找值为****x****的元素。**

**2.** **编写递归算法，在单链表中判断值为****x****的结点是否存在。**

**template <class T>**

**class SeqList**

**\{**

**private:**

**T \*element;//****动态数组存储顺序表元素**

**int size;//****顺序表的数组容量**

**int len;//****顺序表长度**

**public:**

**int search(T x)**

**\{**

**for(int i=0;i<len;i++)**

**\{**

**if(element\[i\]==x) return i;**

**\}**

**return -1;**

**\}**

**template <class T>**

**class Node**

**\{ public:**

**T data;**

**Node<T> \*next;**

**Node()**

**\{**

**this->next = NULL;**

**\}**

**Node(T data, Node<T> \*next = NULL)**

**\{**

**this->data=data;**

**this->next-next;**

**\}**

**\} ;**

**template <class T>**

**class SinglyLinkedList**

**\{**

**public:**

**Node<T> \*head;**

**bool isInList(T x)**

**\{**

**returnisIn(head,x);**

**\}**

**bool isIn(Node<T> \*p ,T x)**

**\{**

**if(p == NULL) return false;**

**if(p->data == x) return true;**

**else return(inIn(p->next,x));**

**\}**

[数据结构]2010数据结构期中考试（c++）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【C语言数据结构1】--数据结构和算法

相关《数据结构》实验课期末考试

相关数据结构考试复习

相关 c语言描述：数据结构【一.数据结构绪论】

相关数据结构C语言代码实战01-数据结构前言

相关【c++】数据结构———堆

相关 [数据结构]2010数据结构期中考试（c++）

相关【C语言】数据结构

相关中国大学MOOC-陈越、何钦铭-数据结构-2019春期中考试

相关中国大学MOOC-陈越、何钦铭-数据结构-2019夏期中考试