24H免费课程咨询  TEL:13401595960   QQ:1870218756  微信:13401595960(李老师)

东方博宜

常州软件开发培训班
网站首页 > 软件开发资讯 > C/C++

线性表常见改错、程序设计、简答、判断题

2017-06-21 22:55:10 东方博宜 阅读

三、改错题

1、 在一个单链表中,已知p所指节点是q所指节点的后继节点,下列语句完成将数据value插入q所指节点之后的功能. 指出错误语句的行号并改正.这里链表结点类型定义为:

struct nodelist

   {

int data;

struct nodelist *next;

   };

   typedef struct nodelist node;

   typedef node *link;

 

01 void insert(int value)

02 {

03    link newnode;

04    newnode=(link)malloc(sizeof(node));

05    newnode->data=value;

06    newnode->next=q;

07    p=newnode;

08 }

 

四、程序设计

1、一个单链表(不同结点的数据域值可能相同),其头指针为head,编写一个函数计算数据域为x的节点个数。

 

2、下面给出一元多项式类型定义:

Struct Item{

   Real Coeff:;

   Int  Exp;

   Struct Iem *Link;

        }

   请给出两个C函数,其中一个为从键盘上输入多项式各个项的系数和指数,建立多项式。按(系数、指数)形式,项的输入顺序任意,以(0,0)作为输入结束标志,另一个为求两个多项式的和。

3、阅读以下算法,填充空格,使其成为完整的算法。其功能是在一个非递减的顺序存储线性表中,删除所有值相等的多余元素。

   #define maxlen 30

   struct sqlisttp

        {

          int elem[maxlen];

          }

   void exam21(sqlisttp L)

   {

j=1;

I=2;

While(         )

{

  if(L.elem[i]!=L.elem[j])

    I=j+1;

}

}

4、给定(已生成)一个带头结点的单链表,设head为头指针,结点的结构为(data,next),data为整数元素,next为指针,试写出算法:按递增次序输出单链表中各结点的数据元素并释放结点所占的存储空间。(要求:不允许使用数组作辅助空间)。

5、假设有两个按元素递增有序排列的线性表A和B,均以单链表作存储结构。请编写算法,将表A和表B归并成一个按元素值非递减有序(允许值相同)排列的线性表C,并要求利用原表(即表A和表B)的结点空间存放表C。

6、下面程序段是合并两条链(f和g)为一条链f的过程。作为参数的两条链都是按结点上number值由小到大链接的。合并后新链仍按此方式链接。请写下述空框,使程序能正确运行。

7、写一算法,将一单链表逆转。要求逆转在原链表上进行,不允许重新构造一个链表。

8、已知非空线性链表第一个结点右list指出,请写一算法,交换p所指结点与其下一个结点在链表中的位置(设p指向的不是链表最后那个结点)。

9、设有一个由正整数组成的无序(向后)单链表,编写能够完成下列功能的算法:

(1)找出最小值结点,且打印该数值;

(2)若该数值是奇数,则将其与直接后继结点的数值交换;

(3)若该数值是偶数,则将其直接后继结点删除。

10、设有头结点的单链表L,编程对表中任一值只保留一个结点,删除其余值相同的结点。

11、假设一个单循环链表,其结点含有三个域pre、data和link。其中data为数据域;pre为指针域,它的值为空指针(NULL);link为指针域,它指向后继结点。请设计算法,将此表改成双向循环链表。(了解)

12、删除一链表中的第 i 个结点,其中 i 的值由用户给定,如果该位置 i不存在要给出提示信息。

13、在头结点为h的单链表中,把值为b的结点s插入到值为a的结点之前,若不存在a,就把结点s插入到表尾。

14、设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B,使A中含有原链表中序号为奇数的元素,而B中含有原链表中序号为偶数的元素,并且保持元素原有的相对顺序。

15、设线性表中的数据元素是按值非递减有序排列的,试以不同的存储结构,编写一算法,将x插入到线性表的适当位置上,以保持线性表的有序性。

16、假设有A和B分别表示两个递增有序排列的线性表集合(即同一表中元素值各不相同), 求A和B的交集C, 表C中也依值递增有序排列。试以不同的存储结构编写求得C的算法。

17设计一个算法求两个递增有序排列的线性表A和B 的差集。(每个单链表中不存在重复的元素)

18、设有线性表A=(a1 ,a2 ,...,am ),B=(b1 ,b2 ,...,bn )。试写一合并A、B为线性表C的算法,使得

                  (a1 ,b1 ,...,am ,bm ,bm+1 ,...,bn 当m≤n时

             C={                                       

                  (a1 ,b1 ,...,an ,bn ,an+1 ,...,am 当m>n时

A、  B和C均以单链表作存储结构,且C表利用A和B中结点空间。

  19、试用两种线性表的存储结构来解决约瑟夫问题。设有n个人围坐在圆桌周围,现从第s个人开始报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m个人又出列,…,如此重复直到所有的人全部出列为止。例如当n=8,m=4,s=1,得到的新序列为:4,8,5,2,1,3,7,6。写出相应的求解算法。

20、已知单链表中的数据元素含有三类字符(即:字母字符、数字字符和其它字符),试编写算法构造三个环形链表,使每个环形链表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。

 

五、简答题

1、在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知头指针,能否将结点

*p从相应的链表中删除?若可以其时间复杂度各为多少?

2、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?

3、描述以下三个概念的区别:头指针、头结点、首元结点(第一个元素结点)。在单链表中设置头结点的作用是什么?

4、线性表有两种存储结构:一是顺序表,二是链表,试问:

(1)    如果有n个线性表同时共存,并且在处理过程中各表的长度会动态地发生变化,线性表的总数也会自动地改变。在此情况下,应选用哪种存储结构?为什么?

(2)    若线性表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取线性表中的元素,那么应采用哪种存取结构?为什么?

5、频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构?为什么?

6、线性表的顺序存储结构具有三个弱点:其一,在作插入和删除操作时,需移动大量元素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。线性表的链式存储结构是否一定能够克服上述三个弱点,试讨论之。

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

  8、链表所表示的元素是否是有序的?如果有序,则有序性体现在何处?链表所表示的元素是否一定要在物理上是相邻的?有序表(顺序表)有序性又如何理解?

 9、用线性表的顺序存储结构来描述一个城市的设计和规划是否合适?为什么?

 10、假设本测试中使用的链表结点定义如下:

 

struct List

{ int data;

  struct List *next;

};

 

typedef  struct List Node;

typedef  Node  *Link;

 

Link P,Q,R,S,head;

Link  pointer,back,new;

对以下单链表分别执行下列程序段,要求分别画出结果图

图片.png

(1)Q=head->next->next;

(2)R->data=P->data;

(3)R->data=P->next->data;

(4)S=P;

    while(S->next!=NULL)

     {  S->data=S->data*2;  S=S->next;}

(5)S=P;

    while(S!=NULL)

{  S->data=S->data*2; S=S->next;}

11、定义同上图

画出执行如下程序段后各指针及链表的示意图

head=(Link)malloc(sizeof(Node));

head->data=0;

head->next=NULL;

P=head;

for(i=1;i<4;i++)

   { new=(Link)malloc(sizeof(Node));

     new->data=2*i;

     new->next=NULL;

     P->next=new;

     P=new;

  }

12、有一链表如下图所示,阅读程序给出程序的输出结果

图片.png

P = head;

while(P != NULL)

  {

     printf(“\n data=%d”, P -> data);

     P = P->next;

     if( P != NULL)

         P = P ->next;

 }

13、链表和指针如图所示,删除pointer指针所指的节点,写出相关语句

图片.png

 

14、描述以下四个概念的区别:头指针变量,头指针,头结点,首结点(第一个结点)。

15、简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。

16、设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个地址空间,求A[3][3](10)存放在什么位置?

17、将以下稀疏矩阵进行压缩,请写出压缩后的数组内容。

    0 0 1 0 0 0

    0 0 0 0 8 0

    0 0 0 3 0 0

    6 0 0 0 0 0

    0 0 0 0 0 4

    0 5 0 0 0 0

    0 0 0 0 0 0

 

 

六、判断正误

(    )1. 链表的每个结点中都恰好包含一个指针。 

(    )2. 链表的物理存储结构具有同链表一样的顺序。

(    )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动将后续各个单元向前移动。

(    )4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。

(    )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。

(    )6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。

(    )7. 线性表在物理存储空间中也一定是连续的。

(    )8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。

(    )9. 顺序存储方式只能用于存储线性结构。

(    )10. 线性表的逻辑顺序与存储顺序总是一致的。

(    )11、性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。

(    )12、具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点。

(    )13、序存储的线性表可以随机存取。

(    )14、在单链表中,要访问某个结点,只要知道该结点的指针即可;因此,单链表是一种随机存取结构。

(    )15、在线性表的顺序存储结构中,插入和删除元素时,移动元素的个数与该元素的位置有关。

顺序存储结构属于静态结构,链式结构属于动态结构。


Powered by 东方博宜教育咨询江苏有限公司  ©2008-2017 www.czos.cn