数据结构_线性表（习题）
2-1
顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。
A.110
B.108
C.100
D.120
2-2
在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。
A.访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B.在第i个结点后插入一个新结点（1≤i≤n）
C.删除第i个结点（1≤i≤n）
D.将n个结点从小到大排序
2-3
向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ ）。
A.8
B.63.5
C.63
D.7
2-4
链接存储的存储结构所占存储空间（ ）。
A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B.只有一部分，存放结点值
C.只有一部分，存储表示结点间关系的指针
D.分两部分，一部分存放结点值，另一部分存放结点所占单元数
2-5
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
2-6
线性表L在（ ）情况下适用于使用链式结构实现。
A.需经常修改L中的结点值
B.需不断对L进行删除插入
C.L中含有大量的结点
D.L中结点结构复杂
2-7
单链表的存储密度（ ）。
A.大于1
B.等于1
C.小于1
D.不能确定
2-8
将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.n
B.2n-1
C.2n
D.n-1
2-9
在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素。
A.n-i
B.n-i+1
C.n-i-1
D.i
2-10
创建一个包括n个结点的有序单链表的时间复杂度是（ ）。
A.O(1)
B.O(n)
C.O(n2)
D.O(nlog2n)
2-11
在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。
A.s->next=p+1; p->next=s;
B.(*p).next=s; (*s).next=(*p).next;
C.s->next=p->next; p->next=s->next;
D.s->next=p->next; p->next=s;
2-12
在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。
A.p->next->prior=p->prior; p->prior->next=p->next;
B.p->next=p->next->next; p->next->prior=p;
C.p->prior->next=p; p->prior=p->prior->prior;
D.p->prior=p->next->next; p->next=p->prior->prior;
2-13
在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。
A.p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;
2-14
已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）。[2013-1]
A.O(n)
B.O（m*n）
C.O(min(m,n))
D.O(max(m,n))
2-15
已知一个带头结点的双向循环链表L，结点结构为（prev，data，next），其中，prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是（ ）。[2016-2]
A.p->next->prev=p->prev; p->prev->next=p->prev; free(p);
B.p->next->prev=p->next; p->prev->next=p->next; free(p);
C.p->next->prev=p->next; p->prev->next=p->prev; free(p);
D.p->next->prev=p->prev; p->prev->next=p->next; free(p);
2-16
已知指针h指向一个带头结点的非空单循环链表，结点结构为（data，next），其中next是指向直接后继结点的指针，p是尾指针，q为临时指针。现要删除该链表的第一个元素，正确的语句序列是（ ）。[2021-1]
A.h->next=h->next->next; q=h->next; free(q);
B.q=h->next; h->next=h->next->next; free(q);
C.q=h->next; h->next=q->next; if(p!=q) p=h; free(q);
D.q=h->next; h->next=q->next; if(p==q) p=h; free(q);
5-1有序表合并
函数merge用于将两个顺序存储的严格递增有序表合并成一个严格递增有序表。如“1，2，3，4”和“2，3，5 ，8，10”合并成“1，2，3，4，5，8，10”。
int merge(int a[], int n1, int b[], int n2, int c[]) // n1为a中元素长度，n2为b中元素长度，返回合并后c中长度
{
int i = 0, j = 0, k = 0;
while (i < n1 && j < n2)
{
if (a[i] < b[j])
c[k++] = a[i++]; // 将a[i]的值放入c，并将i自增
else if (a[i] > b[j])
c[k++] = b[j++]; // 将b[j]的值放入c，并将j自增
else // a[i] == b[j]，避免重复，将a[i]（或b[j]）放入c，i和j都自增
{
c[k++] = a[i++];
j++;
}
}
// 将剩余的a[]中元素放入c[]
while (i < n1)
c[k++] = a[i++];
// 将剩余的b[]中元素放入c[]
while (j < n2)
c[k++] = b[j++];
return k; // 返回合并后c[]的长度
}
5-2奇偶排序
本题目是程序填空题，完成将一个顺序表中的元素按照奇数在前，偶数在后的方式排序。输入数据以0做结束。
#include <iostream>
using namespace std;
typedef int ElemType;
#define M 100
typedef struct
{
ElemType data[M];
int length;
} SeqList;
void ListInit(SeqList &L)
{
L.length = 0; // 初始化顺序表长度为0
}
void CreatList(SeqList &L)
{
int i = 0;
ElemType x;
cin >> x;
while (x)
{
L.data[i] = x; // 将输入的元素存入顺序表
i++;
L.length++; // 每插入一个元素，更新顺序表长度
cin >> x; // 继续读取下一个元素
}
}
void JiOusort(SeqList &L)
{
int i, j;
ElemType t;
i = 0;
j = L.length - 1; // 初始化双指针，i从头开始，j从尾部开始
while (i < j)
{
while (i < j && L.data[i] % 2 != 0)
i++; // 找到第一个偶数
while (i < j && L.data[j] % 2 == 0)
j--; // 找到最后一个奇数
if (i < j)
{
// 交换奇数和偶数
ElemType t = L.data[i];
L.data[i] = L.data[j];
L.data[j] = t;
}
}
}
void OutList(SeqList L)
{
int i = 0;
while (i < L.length)
{
cout << L.data[i] << " "; // 输出顺序表中的元素
i++;
}
cout << endl;
}
int main()
{
SeqList L;
ListInit(L); // 初始化顺序表
CreatList(L); // 创建顺序表
JiOusort(L); // 按奇偶排序
OutList(L); // 输出结果
return 0;
}
原文地址：https://blog.csdn.net/weixin_73699318/article/details/142702533
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！