这篇文章上次修改于 241 天前,可能其部分内容已经发生变化,如有疑问可询问作者。

选择题

  1. 设指针变量front表示链式队列的队头指针,指针变量rear表示链式队列的队尾指针,指针变量s指向将要入队列的结点X,则入队列的操作序列为

D C

涂,没看到是队列

s->next = front;
front = s;

// 真解
rear->next = s;
rear = s;
  1. 设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是

B A

head-next == 0;
// 真解 ,判断为空
head == 0;

// 有头节点,没有顺序节点
head->next == 0
  1. 一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是

A

3 1 2
  1. 设一个有序的单链表中有n个结点,现要求插入一个新结点后使得单链表仍然保持有序,则该操作的时间复杂度为( )。

D

循环找到相应节点,最坏情况 循环 n 次
  1. 设循环队列的元素存放在一维数组A[0..40]中,队列非空时,front指示队首元素,rear指示队尾元素的后一个位置。如果队列中元素的个数为15,front的值为33,则rear应指向的位置是

C

$$ 15 + 33 - 40 - 1 = 7 $$

  1. 广义表A = (a,(b),(),(c,d,e,f))的长度为

B

// 广义表中的元素可以为 各种
  1. 从广义表LS =((a, b), c, d)中分解出原子b的运算是

C

head(tail(head(LS)))
  1. 二维数组$A[12][18]$采用以列为主优先存储方法,若每个元素各占3个存储单元,且第1个元素的地址为150,则元素$A[10][8]$的地址为

B D

原来是 列 x 行元数

$$ (8 * 12 + 10) * 3 + 150 = 468 $$

  1. 在数据结构中,数据的逻辑结构可以分成

C

线性结构 和 非线性结构

  1. 以下与数据的存储结构无关的术语是

A B

栈不是

  1. 若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是

A

5出了,4都没出,1出个毛线

$$ 2, 3, 5 ,1, 6, 4 $$

  1. 下列各项中属于逻辑结构的是

A C

小猜一手

// 顺序表 顺序存储结构
// 单链表、哈希表都为存储结构
// 有序顺序表,为逻辑结构
  1. 将一个长度为n的单链表链接到一个长度为m的单链表之后,该算法的时间复杂度为

B

// 只需要 接个尾巴 + 头 1次即可,当然如果是没有尾巴节点,需要循环到一个的末尾,但是从选项来看,不得,所以就只 1次了
  1. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串,函数Scopy(s,t)的功能为复制串t到s。若字符串S=“SCIENCESTUDY”,则调用函数Scopy(P,Sub(S,1,7))后,得到

A

st=>start: SCIENCE
e=>end: 复制一个 A

st->e
  1. 设计一个判别表达式中左,右括号是否配对出现的算法,采用( )数据结构最佳

D

​ 用足想,都是 栈喽

填空题

  1. 一个12阶对称矩阵A,采用行优先顺序存储压缩存储上三角元素,a00为第一个元素,其存储地址为100,每个元素占2个存储地址空间,则a45的地址为

186

​ 按行优先,第一行 12个,第二行 11个..... 前四行有 $12 + 11 + 10 + 9 = 42$个

而,到了第五行,开头第一个处于第五列。

$$ (42+1)*2 + 100 = 186 $$

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

3

​ 显而易见,最多的时候就是 S1 S5 S6

  1. 带头结点的双向循环链表L为空的条件是:

L->next == NULL

L->next == L 或 L->prior==L

  1. 假设为循环队列分配的向量空间为Q[30],若队列的长度和队首指针分别为15和19,则当前队尾指针的值为_______(备注:队首指针指向队首元素所在的位置,队尾指针指向队尾元素的下一个位置)。

5 4

  1. 表达式求解是_______应用的一个典型例子

  1. 设有一批数据元素,为了最快地存取其中某元素,宜采用________结构存储;为了方便中间插入一个元素,宜采用________结构存储。

顺序

链式

  1. 假设一个10阶的下三角矩阵A按列优先顺序压缩存储在一维数组C中,则数组C的大小为______

55

$$ 1 + 2 +3 + 4 +5 + 6 +7 + 8 + 9 + 10 = 55 $$

  1. 广义表A=(y,(z,w),(x,(z,w),a))的表尾为______,深度为______。

a

4

  1. 数据的基本单位是______,有时它可以由若干个______组成。

​ 数据元素、数据项

  1. 设有顺序存储的长度为n的线性表,在等概率情况下,插入一个元素时平均需要移动______个元素,删除一个元素时平均需要移动______元素。

$n/2$

$n/2$

程序功能题

三、已知顺序栈s,简述func函数的功能,当输入80时,输出结果是多少?

func( )
{  initstack(s);
scanf(“%d”,&n);
while(n)
     { push(s, n%8);  n=n/8; } 
while(!Emptystack (s)) 
{ pop(s,x); printf(“%d”,x); } 
    }

1

2

0

四、已知一个带头结点的非空单循环链表,其结点按数据域值从大到小顺序排列,L为头指针,尾结点的指针域指向头结点。函数InsertList用于将一个数据域为x的结点s插入至该循环链表的适当位置使之仍保持有序。请将函数补充完整。

typedef struct node
{ 
int data;
  struct node *next;
}LNode,*LinkList;

void InsertList(LinkList &L,int x)
{ LNode *s,*p,*q;
 s=new LNode;
 s->data=x;
 p=L;
 _____①_______;
 while( ____②_______ &&___③______ )
  { p=p->next;
   q=q->next;
  }
 ____④______;
____⑤______;
}
typedef struct node
{ 
int data;
  struct node *next;
}LNode,*LinkList;

void InsertList(LinkList &L,int x)
{ LNode *s,*p,*q;
 s=new LNode;
 s->data=x;
 p=L;
 q=L->next;
 while( q->data>x && q!=L)
  { p=p->next;
   q=q->next;
  }
  s->next = q;
  p->next = s;
}

五、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。

其中结点的存储结构如下图所示:

datanext
#include<ctype.h>
//isdigit和isalpha必须要头文件<ctype.h>
//测试输入值是否为数字或字母

//结点的结构类型定义如下:
    typedef char datatype;
    typedef struct node 
   {
     datatype data; 
     struct node *next;
}lklist;
//三类不同的元素分别存入到三个不同的链表中,请补充完整下列函数:
void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)
{
    lklist *r1, *r2, *r3, *p;
    r1 = ha->next;
    r2 = hb->next;
    r3 = hc->next;
    while(head->next != NULL)
    {
        // 如果是数字
        if(isdigit(head->next->data))
        {
            r1->next = head;
            r1 = head;
        }
        // 如果是字母
        else if(isalpha(head->next->data))
        {
            r2->next = head;
            r2 = head;
        }
        else{
            r3->next = head;
            r3 = head;
        }
    }
    r1->next = NULL;
    r2->next = NULL;
    r3->next = NULL;
}

六、设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构)的适当位置上,并保持线性表的有序性。

#define MaxSize 100 
typedef struct {
    ElemType data [MaxSize];
    int Length;
} Para;

void Insert(Para *& r, ElemType x)
{
    int i = 0;
    for(; i < r->Length; i++)
    {
         if(x > r->data[i])
             break;     
    }
    for(int j = r->Length; j > i; j--)
    {
        r->data[j] = r->data[j - 1];
    }
    r->data[i] = x;
    r->Length++;
}