数据结构 线性表试题

《数据结构 线性表试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构线性表试题　选择题1．对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间A）顺序表B）带头结点的双循环链表C）单链表D）带尾结点的单循环链表【答案】A2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（　　）(1≤i≤n+1)。A）O(0)B）O(1)C）O(n)D）O(n2)【答案】C3．双向链表中有两个指针域，prior和next，分别指向前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（）A）p->prio

2、r=q;q->next=p;p->prior->next=q;q->prior=p->prior;B）q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;C）q->next=p;p->next=q;p->prior->next=q;q->next=p;D）p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;【答案】D4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）A

3、）O(nlog2n）B）O(1）C）O(n）D）O(n2）【答案】C5．在一个以h为头指针的单循环链中，p指针指向链尾结点的条件是（）A）p->next==NULLB）p->next==hC）p->next->next==hD）p->data==-1【答案】B6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（　　）A）O(n)B）O(1)C）O(nlog2n)D）O(n2)【答案】A8．在双向链表存储结构中，删除p所指的结点时须修改指针（　　）A）p->prior->next=p->nextp->next->prio

4、r=p->prior;B）p->prior=p->prior->priorp->prior->next=p;C）p->next->prior=pp->next=p->next->nextD）p->next=p->prior->priorp->prior=p->next->next;【答案】A9．线性表采用链式存储时，其元素地址（　　）A）必须是连续的B）一定是不连续的C）部分地址是连续的D）连续与否均可【答案】D2.2　填空题1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要

5、移动元素的个数是_____________。【答案】（n-1）/22．在单链表中设置头结点的作用是_____________。【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。3．线性表的顺序存储是通过_____________来反应元素之间的逻辑关系，而链式存储结构是通过_____________来反应元素之间的逻辑关系。【答案】（1）数据元素的前后顺序（2）元素中的指针4．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用_

6、____________存储结构最节省时间，相反当经常进行插入和删除操作时，则采用_____________存储结构最节省时间。【答案】（1）顺序（2）链式5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_____________，在给定值为x的结点后插入一个新结点的时间复杂度为_____________。【答案】（1）O(1)（2）O(n)7.对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____________个，单链表为_____________个。【答案】（1）4（2）28.循

7、环单链表的最大优点是_____________。【答案】从任一结点出发都可访问到链表中每一个元素。9．若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时，可执行下列操作：s->next=_____________;p->next=s;t=p->data;p->data=_____________;s->data=_____________;【答案】（1）p->next（2）s->data（3）t10．某线性表采用顺序存储结构，每个元素占据4个存储单元，首地址为100，则下标为11的（第12个）元素的存储地址为__

8、___________。【答案】14411．带头结点的双循环链表L中只有一个元素结点的条件是_____________。【答案】L->next->next==L2.3　判断题1．取线性表的第i个元素的时间同i的大小有关（　　）【答案】×2．线性表的特点是每个元素