单项选择(2015年春程序员软考)

含有n个元素的线性表采用顺序存储,等概率删除其中任一个元素,平均需要移动【 】个元素。

A、n

B、logn

C、(n-1)/2

D、(n+2)/2

答案解析

C

【解析】

在表长为n的线性表中删除一个元素时,共有n个可删除的元素。删除a1时需要移动n-1个元素,删除an时不需要移动元素,因此,等概率下删除一个元素时平均的移动元素个数Edelete

Edelete=∑qi×(n-i)=1/n·∑(n-i)=(n-1)/2

其中,qi表示删除第i个元素(ai)的概率。

讨论

已知字符串s='(X+Y)*Z',其中,单引号不是字符串的内容,经过以下运算后,t3的值是【 】。t1= SubString(s,3,1)t2=Concat('XY', t1)t3=Replace(s,SubString(s,1,5),t2)注: SubString(s,k,n)表示从串s的第k个字符开始取出长度为n的子串, Concat(s,t)表示将串t连接在s之后, Replace(s,t,r)表示用r替换串s中的子串t。

在解决计算机与打印机之间速度不匹配的问题时,通常设置一个打印数据缓冲区,计算机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区取出数据。因此,该缓冲区的数据结构应该是【 】。

算术表达式a+(b-c)*d的后缀式是【 】(-、+、*表示算术的减、加、乘运算,运算符的优先级和结合性遵循惯例)。

阅读以下说明和C函数,填补代码中的空缺(1)~(6)。二叉树的宽度定义为含有结点数最多的那一层上的结点数。函数 GetWidth()用于求二叉树的宽度。其思路是根据树的高度设置一个数组 counter[], counter[i]存放第i层上的结点数,并按照层次顺序来遍历二又树中的结点,在此过程中可获得每个结点的层次值,最后从counter[]中取出最大的元素就是树的宽度。按照层次顺序遍历二叉树的实现方法是借助一个队列,按访问结点的先后顺序来记录结点,离根结点越近的结点越先进入队列,具体处理过程为:先令根结点及其层次号(为1)进入初始为空的队列,然后在队列非空的情况下,取出队头所指示的结点及其层次号,然后将该结点的左子树根结点及层次号入队列(若左子树存在),其次将该结点的右子树根结点及层次号入队列(若右子树存在),然后再取队头,重复该过程直至完成遍历。设二叉树采用二叉链表存储,结点类型定义如下:typedef struct BTNode{ TElemType data; struct BTNode *left, *right;}BTNode, *BiTree;队列元素的类型定义如下:typedef struct{ BTNode *ptr; int LevelNumber;}QElemType;Get Width()函数中用到的函数原型如下所述,队列的类型名为 QUEUE:InitQueue(QUEUE *Q):初始化一个空队列,成功时返回值为1,否则返回值0isEmpty(QUEUE Q):判断队列是否为空,是空则为1,否则为0EnQueue( QUEUE*Q, QElemType a):将元素a加入队列,成功返回值为1,否则返回值0DeQueue(QUEUE *Q, QElemType *):删除队头元素,并通过参数带回其值,成功则返回值1,否则返回值0GetHeight (BiTree root):返回值为二叉树的高度(即层次数,空二叉树的高度为0)int Getwidth(BiTree root){ QUEUE Q; QElemType a, b; int width,height= GetHeight(root); int i, *counter =(int *)calloc(height+1, sizeof (int)); if(__(1)__) return -1;/*申请空间失败*/ if(! root) return 0;/*空树的宽度为0*/ if(__(2)__) return -1;/*初始化队列失败时返回*/ a.ptr= root; a.LevelNumber=1; if(! EnQueue(&Q,a)) return -1;/*元素入队列操作失败时返回*/ while (! isEmpty(Q)){ if(__(3)__)return -1;/*出队列操作失败时返回*/ counter[b. LevelNumber]++;/*对层号为b. LevelNumber的结点计数*/ if(b.ptr->left){/*若左子树存在,则左子树根结点及其层次号入队*/ a.ptr= b.ptr->left; a.LevelNumber=__(4)__; if(!EnQueue(&Q,a)) return -1; } if(b.ptr-> right){/*若右子树存在,则右子树根结点及其层次号入队*/ a.ptr= b.ptr->right; a. LevelNumber=__(5)__; if(! EnQueue(&Q,a)) return -1; } } width= counter[1]; for(i=1; i< height +1; 1++)/*求 counter[]中的最大值*/ if(__(6)__)width= counter [i]; free(counter); return width;}

阅读以下说明和C函数,填补函数代码中的空缺(1)~(5)。队列是一种常用的数据结构,其特点是先入先出,即元素的插入在表头、删除在表尾进行。下面采用顺序存储方式实现队列,即利用一组地址连续的存储单元存放队列元素,同时通过模运算将存储空间看作一个环状结构(称为循环队列)。设循环队列的存储空间容量为 MAXQSIZE,并在其类型定义中设置base、rear和 length三个域变量,其中,base为队列空间的首地址,rear为队尾元素的指针, length表示队列的长度。#define MAXQSIZE 100typedef struct{ QElemType *base;/*循环队列的存储空间首地址* int real;/*队尾元素索引*/ int ength;/*队列的长度*/} SqQueue;例如,容量为8的循环队列如下图所示,初始时创建的空队列如图(a)所示,经过一系列的入队、出队操作后,队列的状态如图(b)所示(队列长度为3)。 下面的C函数1、C函数2和C函数3用于实现队列的创建、插入和删除操作,请完善这些代码。【C函数1】创建一个空的循环队列int InitQueue (SqQueue *Q){ /*创建容量为 MAXQSIZE的空队列,若成功则返回1;否则返回0*/ Q->base =(QElemType *)malloc( MAXQSIZE*__ (1)__); if (! Q->base) return 0: Q->length=0; Q->rear =0; return 1;}/* InitQueue*/【C函数2】元素插入循环队列。int EnQueue( SqQueue *Q, QElemType e){/*元素e入队,若成功则返回1;否则返回0*/ if( Q->length>=MAXQSIZE) return 0; Q->rear=__(2)__; Q->base [Q->rear]=e; __(3)__; return 1;}/*EnQueue*/【C函数3】元素出循环队列。int DeQueue (SqQueue *Q,QElemType *e){ /*若队列不空,则删除队头元素,由参数e带回其值并返回1;否则返回0*/ if(__(4)__)return 0; *e=Q-base[(Q->rear-Q->length+1+MAXQSIZE)%MAXQSIZE]; __(5)__; return 1;}/*DeQueue*/

在数据结构中,【 】是与存储结构无关的术语。

设有字符串S= "software",其长度为3的子串数目为【 】。

对于一个初始为空的栈,其入栈序列为abc时,其出栈序列可以有【 】种。

含有n个元素的线性表采用顺序存储方式时,对其运算速度最快的操作是【 】。

算术表达式a*(b-c)+d的后缀式是【 】(-、+、*表示算术的减、加、乘运算,运算符的优先级和结合性遵循惯例)。

表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为_______,删除一个元素需要移动元素的平均个数为_______。供选择的答案:A.(n-1)/2 B.n C.n+1 D.n-1 E.n/2 F.(n+1)/2 G.(n-2)/2

在含有n个元素的顺序表中,算法时间复杂度为O(1)的操作是【 】

线性表选用顺序存储结构表示的适用场合是____________________。

顺序表存储方式只能用于存储线性结构。

若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为【 】。(1≤i≤n+1)

设A是一个线性表(a1,a1,...,an),采用顺序存储结构,则在等概率的前提下,平均每插入一个元素需要移动的元素个数为多少?若元素插在ai与ai+1之间(0≤i≤n-1)的概率为,则平均每插入一个元素所要移动的元素个数又是多少?

假设线性表的长度为n,且采用顺序存储结构存储。当在线性表的任何位置上插入一个数据元素的概率相同时,插入一个数据元素需要移动元素的平均个数为【 】。

含有n个元素的线性表用顺序存储方式时,对其运算速度最快的操作是【 】。

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

若某线性表长度为n且采用顺序存储方式,则运算速度最快的操作是【 】。