数据结构

题目

设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:

X (2)-> Y (1)-> Z

1、首先这是一个插入的方法，而第一步就是把将要插入的y结点的下一个结点变为x原来的下一个结点

1	py->next = px->next;

2、把x结点的下一个结点变为x结点

1	px->next = py;

对线性表L=（a1…an）

(1)如L为顺序表，请设计算法将L就地逆置。

#include <iostream>
using namespace std;

const int MAXSIZE = 100;

typedef struct {
    int data[MAXSIZE];
    int length;
} SqList;

// 将顺序表L就地逆置
void reverse(SqList &L) {
    int temp;
    for (int i = 0; i < L.length / 2; i++) {
        temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

int main() {
    SqList L = {{1, 2, 3, 4, 5, 6}, 6}; // 初始化顺序表L
    reverse(L); // 就地逆置L
    for (int i = 0; i < L.length; i++) {
        cout << L.data[i] << " ";
    }
    return 0;
}

(2)若L为带头结点的单链表，设计算法将L就地逆置。

#include <iostream>

using namespace std;



struct ListNode {

    int data;

    ListNode* next;

};

void reverseList(ListNode* L) {



    ListNode* cur = L->next;

    L->next = NULL;



    ListNode* next = cur->next;

    cur->next = L->next;

    L->next = cur;

    cur = next;

}

试编写在带头结点的单链表L中删除（一个）最小值结点的（高效）算法。

#include <iostream>
using namespace std;

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

// 创建带头结点的单链表
void createList(LinkList &L, int a[], int n) {
    L = new LNode;
    L->next = NULL;
    for (int i = n-1; i >= 0; i--) {
        LNode *p = new LNode;
        p->data = a[i];
        p->next = L->next;
        L->next = p;
    }
}

// 删除带头结点的单链表L中最小值结点
void deleteMin(LinkList &L) {
    LNode *pre = L, *p = L->next, *minpre = pre, *minp = p;
    while (p != NULL) {
        if (p->data < minp->data) {
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    delete minp;
}

int main() {
    int a[] = {3, 1, 4, 2, 5};
    LinkList L;
    createList(L, a, 5); // 创建带头结点的单链表L
    deleteMin(L); // 删除L中最小值结点
    LNode *p = L->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    return 0;
}

设有一个带头结点的单链表，其结点的数据值均为正整数，编写完成下列功能的算法：

(1)找出最小值结点，且输出该数值；

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

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

#include<bits/stdc++.h>

using namespace std;



struct ListNode {

    int data;

    ListNode* next;

};



void swapdataue(ListNode* a, ListNode* b) {

    int temp = a->data;

    a->data = b->data;

    b->data = temp;

}



void deleteNextNode(ListNode* node) {



    ListNode* del = node->next;

    node->next = del->next;

    delete del;

}



void operateList(ListNode* L) {



    ListNode* pre = L;

    ListNode* cur = L->next;

    ListNode* min_pre = pre;

    ListNode* min = cur;



    if (cur->data < min->data) {

        min_pre = pre;

        min = cur;

    }

    pre = cur;

    cur = cur->next;



    cout << "最小值为：" << min->data << endl;

    if (min->data % 2 == 1 && min->next != NULL) {

        swapdataue(min, min->next);

    }

    else if (min->data % 2 == 0 && min->next != NULL) {

        deleteNextNode(min);

    }

}

假设有两个按元素值非递减次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值非递增次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

#include <iostream>
using namespace std;

// 定义链表结点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 归并两个单链表并返回合并后的链表头节点
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);  // 哑结点
    ListNode* tail = &dummy;  // 合并后链表的尾结点
    while (l1 && l2) {
        // 选择两个链表中较小的结点接入合并后的链表尾部
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        }
        else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    // 将剩余的链表结点接入合并后的链表尾部
    if (l1) {
        tail->next = l1;
    }
    else {
        tail->next = l2;
    }
    // 反转合并后的链表，使其变为非递增次序排列
    ListNode* prev = NULL;
    ListNode* curr = dummy.next;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

int main() {
    // 初始化两个按元素值非递减次序排列的单链表
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);
    l1->next->next->next = new ListNode(7);
    l1->next->next->next->next = new ListNode(9);
    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);
    l2->next->next->next = new ListNode(8);
    l2->next->next->next->next = new ListNode(10);

    // 归并两个单链表并输出合并后的链表元素
    ListNode* merged = mergeTwoLists(l1, l2);
    while (merged) {
        cout << merged->val << " ";
        merged = merged->next;
    }
    cout << endl;

    return 0;
}
//ListNode(int x) : val(x), next(NULL) {} 是一个 C++ 类的构造函数。它的作用是创建一个新的 ListNode 对象，并初始化 val 和 next 属性。

//具体地，: val(x), next(NULL) 是 C++ 中的成员初始化列表，用于给对象的成员变量进行初始化。在这里，val 成员变量被初始化为参数 x 的值，而 next 成员变量被初始化为 NULL。然后，在函数体内部，由于该构造函数不需要进行额外的操作，所以函数体为空。

//总之，这行代码的作用是创建一个新的 ListNode 对象，并将它的 val 属性设置为 x，next 属性设置为 NULL

第三章

利用栈和队列，判断键盘上输入的n个数是否构成回文序列。(算法设计题)

//在代码中，输入序列中的元素通过stack和queue两个数据结构依次入栈和入队。然后，使用top()和front()方法依次从栈和队列中取出元素，并比较它们的值是否相等，如果有不相等的，则说明输入序列不是回文序列，返回false。如果比较到栈和队列都为空，说明输入序列是回文序列，返回true。最后，在main()函数中调用is_palindrome()函数，根据其返回值输出结果。

#include <iostream>
#include <stack>  // 包含栈所在的头文件
#include <queue>  // 包含队列所在的头文件
using namespace std;

// 判断输入的n个数是否构成回文序列
bool is_palindrome(int n) {
    stack<int> s;  // 定义一个整型栈s
    queue<int> q;  // 定义一个整型队列q
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;  // 输入第i个数
        s.push(num);  // 将第i个数入栈
        q.push(num);  // 将第i个数入队
    }
    while (!s.empty() && !q.empty()) {  // 当栈和队列都不为空时
        if (s.top() != q.front()) {  // 如果栈顶元素和队首元素不相等
            return false;  // 返回false，输入的数不是回文序列
        }
        s.pop();  // 将栈顶元素弹出
        q.pop();  // 将队首元素弹出
    }
    return true;  // 如果比较完毕栈和队列都为空，则输入的数是回文序列，返回true
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;  // 输入元素个数
    if (is_palindrome(n)) {  // 如果输入的数是回文序列
        cout << "The sequence is a palindrome." << endl;
    } else {  // 如果输入的数不是回文序列
        cout << "The sequence is not a palindrome." << endl;
    }
    return 0;  // 程序结束，返回0
}

检查表达式中括号是否匹配

//在代码中，输入的表达式字符串通过stack栈结构进行括号匹配检查。当遇到左括号时，将其入栈；当遇到右括号时，从栈中弹出一个元素并比较其是否匹配。如果不匹配，则表达式中的括号不匹配，返回false；如果栈中元素都已匹配完毕，表明表达式中的括号匹配，返回true。最后，在main()函数中调用is_matching()函数，根据其返回值输出结果。

值得注意的是，代码中默认输入的表达式中只包含括号，如果输入的表达式中包含其他字符，则需要做相应的处理。
#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 判断表达式中的括号是否匹配
bool is_matching(string exp) {
    stack<char> s; // 声明一个栈s
    for (int i = 0; i < exp.length(); i++) { // 循环遍历表达式中的每个字符
        char ch = exp[i]; // 获取当前字符
        if (ch == '(' || ch == '{' || ch == '[') { // 如果当前字符是左括号，则入栈
            s.push(ch);
        } else if (ch == ')' || ch == '}' || ch == ']') { // 如果当前字符是右括号，则弹出栈顶元素进行匹配
            if (s.empty()) { // 如果栈为空，则说明右括号没有匹配的左括号，表达式中的括号不匹配，返回false
                return false;
            }
            char top_ch = s.top(); // 获取栈顶元素
            s.pop(); // 弹出栈顶元素
            if ((ch == ')' && top_ch != '(') || // 如果当前字符是右括号，但栈顶元素不是对应的左括号，则表达式中的括号不匹配，返回false
                (ch == '}' && top_ch != '{') || 
                (ch == ']' && top_ch != '[')) {
                return false;
            }
        }
    }
    return s.empty(); // 如果栈中没有剩余元素，则说明表达式中的括号全部匹配，返回true；否则返回false
}

int main() {
    string exp;
    cout << "Enter an expression: ";
    cin >> exp;
    if (is_matching(exp)) { // 调用is_matching()函数判断表达式中的括号是否匹配，并输出结果
        cout << "The parentheses in the expression are matched." << endl;
    } else {
        cout << "The parentheses in the expression are not matched." << endl;
    }
    return 0;
}

利用栈的基本操作实现将十进制整数N转换为r（2≤r≤16）进制数，并输出

#include <iostream>
#include <stack>
using namespace std;

// 将十进制整数N转换为r进制数
void convert(int N, int r) {
    stack<int> s; // 声明一个栈s
    while (N > 0) { // 循环将N转换为r进制数
        int remainder = N % r; // 计算N除以r的余数
        s.push(remainder); // 将余数入栈
        N /= r; // 将N除以r的商作为新的N
    }
    // 将栈中的元素依次弹出并输出，即为r进制表示的N
    cout << "The converted number is: ";
    while (!s.empty()) {
        int digit = s.top(); // 获取栈顶元素
        s.pop(); // 弹出栈顶元素
        if (digit < 10) { // 如果是0-9的数字，则直接输出
            cout << digit;
        } else { // 否则输出对应的字母
            cout << char(digit - 10 + 'A');
        }
    }
    cout << endl;
}

int main() {
    int N, r;
    cout << "Enter a decimal integer N: ";
    cin >> N;
    cout << "Enter a base r (2 <= r <= 16): ";
    cin >> r;
    convert(N, r); // 调用convert()函数进行转换并输出结果
    return 0;
}

学习通

第一章(基础概念)

(单选题) 以下关于数据的存储结构的叙述中哪一条是正确的（）。

A. 数据的存储结构是逻辑结构在计算机存储器中的实现
B. 数据的存储结构对数据运算的具体实现没有影响
C. 数据的存储结构是数据间关系的抽象描述
D. 数据的存储结构分为线性结构和非线性结构

（数据的逻辑结构分为线性结构和非线性结构两大类，线性结构包括数组、链表、栈、队列等; 非线性结构包括树、图等）

我的答案: A:数据的存储结构是逻辑结构在计算机存储器中的实现;正确答案: A:数据的存储结构是逻辑结构在计算机存储器中的实现;

B. 数据的存储结构对数据运算的具体实现没有影响：这个选项是错误的。数据的存储结构会对数据的运算和操作产生影响。不同的存储结构会影响数据的访问效率、插入和删除操作的复杂度等。

C. 数据的存储结构是数据间关系的抽象描述：这个选项是不准确的。数据的存储结构描述的是数据在计算机存储器中的组织方式，它并不仅仅是对数据间关系的抽象描述，还包括数据的物理存储方式和访问方式等。

D. 数据的存储结构分为线性结构和非线性结构：这个选项是不准确的。数据的存储结构可以更细分为线性结构、树形结构、图形结构等多种类型，而非线性结构只是其中的一种。

(单选题) 下面说法错误的是（）

A. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法
B. 同一个算法，实现语言的级别越高，执行效率就越低
C. 算法原地工作的含义是指不需要任何额外的辅助空间
D. 所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界

我的答案: B:同一个算法，实现语言的级别越高，执行效率就越低;正确答案: C:算法原地工作的含义是指不需要任何额外的辅助空间;（和AI有歧义）

(填空题) 数据的（）在计算机中的表示（映像）称为存储结构，需要考虑数据元素的表示和数据元素间关系的表示。数据的存储结构分为（）、（）、索引和散列存储结构。

我的答案：

(1) 存储结构

(2) 顺序存储结构

(3) 链式存储结构
正确答案：

(1) 逻辑结构

(2) 顺序

(3) 链式

数据的逻辑结构是指。

我的答案：

(1) 逻辑结构在计算机存储器中的实现
正确答案：

(1) 数据的组织形式，即数据元素之间逻辑关系的总体

（数据的逻辑结构分为线性结构和非线性结构两大类，线性结构包括数组、链表、栈、队列等; 非线性结构包括树、图等）

(填空题) 一个算法具有5个特性： , , ，有零个或多个输入、有一个或多个输出。

我的答案：

(1) 有穷性

(2) 确定性

(3) 可行性
正确答案：

(1) 有穷性

(2) 确定性

(3) 可行性

下面程序段中带下划线的语句的执行次数的数量级是。i=1；while( i<n) i=i*2;

我的答案：**0分

(1) O（log₂n）
正确答案：

(1) O(log2n)

(填空题) 下面程序段中x++的语句的执行次数的数量级是。i=1；while( i<n) {for (j=1;j<=n;j++) x++i=i*2;}

我的答案：

(1) O（nlog₂n）
正确答案：

(1) O(nlog2n)

(判断题) 算法可以用不同的语言描述，如果用C 语言或C++语言等高级语言来描述，则算法实际上就是程序了。

A. 对
B. 错

我的答案: 错正确答案: 对

数据结构的操作的定义与具体实现有关。

A. 对
B. 错

我的答案: 对正确答案: 错

(判断题) 数据项是数据不可分割的最小单位。

A. 对
B. 错

我的答案: 对正确答案: 对

第二章（线性表）

(单选题) 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（）最节省时间。

A. 单链表
B. 单循环链表
C. 带尾指针的单循环链表
D. 带头指针的单循环链表

我的答案: D:带头指针的单循环链表;

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

A. O(0)
B. O(1)
C. O(n)
D. O()

我的答案: C

(单选题) 线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。

A. O（i）
B. O（1）
C. O（n）
D. O（i-1）

我的答案: C:O（n）;

(单选题) 非空的循环单链表head的尾结点p满足（）。

A. p->next==head
B. p->next==NULL
C. p==NULL
D. p= head

我的答案: A:p->next==head;

(单选题) 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。

A. p->next=s;s->next=p->next;
B. s->next=p->next;p->next=s;
C. p->next=s;p->next=s->next;
D. p->next=s->next;p->next=s;

我的答案: B:s->next=p->next;p->next=s;；

(单选题) 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。

A. head==NULL
B. head->next==NULL
C. Head->next==head
D. head!=NULL

我的答案: B:head->next==NULL;

(单选题) 完成在非空双向循环链表结点p之后插入s的操作是（）。

A. p->next=s ; s->prior=p; p->next->prior=s ; s->next=p->next;
B. p->next->prior=s; p->next=s; s->prior=p; s->next=p->next;
C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;
D. s->next=p->next; p->next->prior=s ; s->prior=p; p->next=s;

我的答案: C:s->prior=p; s->next=p->next; p->next=s; p->next->prior=s ;;

(单选题) 在双向循环链表中，删除p所指的结点时须修改指针（）。

A. p->prior->next=p->next； p->next->prior=p->prior;
B. p->prior=p->prior->prior ； p->prior->next=p;
C. p->next->prior=p； p->next=p->next->next;
D. p->next=p->prior->prior； p->prior=p->next->next;

我的答案: A:p->prior->next=p->next； p->next->prior=p->prior;;

线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（）。

我的答案：

(1) (n-1)/2

(填空题) 在一个长度为n的顺序表中第i个位置（1≤i≤n+1）插入一个元素时，需向后移动（）个元素。

我的答案：

(1) n - i + 1

第三章

全是算法

第四章（栈和队列）

(单选题)栈和队列的共同点是( )。

A. 没有共同点
B. 只允许在端点处插入和删除元素
C. 都是先进后出
D. 都是先进先出

我的答案: B:只允许在端点处插入和删除元素;

(单选题) 循环队列占用的空间( )。

A. 必须连续
B. 不必连续
C. 不能连续
D. 可以不连续

***的答案: A 正确答案: A

4.(单选题) 若用一个大小为6的数组来实现循环队列,且当前front和rear的值分别为3和0,当从队列中删除一个元素,再加入两个元素后,front和rear的值分别为( )。

A. 5和1
B. 4和2
C. 2和4
D. 1和5

***的答案: B 正确答案: B

(单选题) 对于队列操作数据的原则是( )。

A. 先进先出
B. 后进先出
C. 先进后出
D. 不分顺序

***的答案: A 正确答案: A

(单选题) 设链栈中结点的结构:data为数据域,next为指针域,且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点,则应执行下列( )操作。

A. s->next=top->next;top->next=s;
B. top->next=s;
C. s->next=top;top=top->next;
D. s->next=top;top=s;

***的答案: D 正确答案: A

(单选题) 队列中的元素个数是( )。

A. 不变的
B. 可变的
C. 任意的
D. 0

***的答案: B 正确答案: B

17.(单选题) 循环队列SQ队满的条件是( )。

A. SQ->rear==SQ->front
B. (SQ->rear+1)%MAXLEN==SQ->front
C. SQ->rear==O
D. SQ->front==0

***的答案: B 正确答案: B

(填空题) 顺序队列初始化后, front=rear=___。

***的答案：

(1) 1
正确答案：

(1) -1

(填空题) 在队列中,允许插入的一端称为___。

***的答案：

(1) 队尾
正确答案：

(1) 队尾

(填空题) 在队列中,允许删除的一端称为___。

***的答案：

(1) 队首
正确答案：

(1) 队头

(判断题) 栈和队列都是顺序存储的线性结构。

A. 对
B. 错

***的答案: 错正确答案: 错

第五章（串和广义表）

(单选题)广义表(a,b,c,d,e)的表尾是( )。

A. (e)
B. ( )
C. (b,c,d,e)
D. (a,b,c,d,e)

我的答案: C

(单选题)广义表是线性表的推广,它们之间的区别在千( )。

A. 能否使用子表
B. 能否使用原子项
C. 是否能为空
D. 表的长度

我的答案: A:能否使用子表;

(单选题)设有一个字符串S=”abcdefgh”,问该串的最大子串个数为( )。

37=(8*9)/2+1

A. 9
B. 37
C. 36
D. 8

我的答案: B:37;

串的最大子串个数计算

字串： n（n+1）/2 + 1

非空子串：n（n+1）/2

非空真子串：n（n+1）/2 - 1

(单选题)若Strlndex(S,T)表示求T在S中的位置的操作,则对于S=”Beijing and Nanjing”,T=”jing”,Strlndex(S,T)的结果为( )。

A. 4
B. 2
C. 3
D. 16

正确答案: A

(填空题)串链接存储的优点是（）,缺点是（）。

我的答案：

(1) 可以任意地插入和删除子串，不需要移动其他子串

(2) 存储密度低，每个字符都需要一个指针来指向下一个字符，因此浪费了大量的存储空间

(填空题)串顺序存储紧凑格式的缺点是对串的字符处理___。

我的答案：

(1) 比较困难

(填空题)空格串的长度等于___。

我的答案：

(1) 空格的个数

(填空题)在C语言中,以字符___表示串值的终结。

我的答案：

(1) ’\0’

串的函数

ConcatStr(S1,S2)直接拼接S1和S2

SubStr(S1,2,LenStr(S2))选取

Strlndex(S,T)返回字符串t在字符串s中出现的开始位置或索引。

(填空题)两个串相等是指两个串长度相等,且对应位置的___相等。

我的答案：

(1) 字符

(填空题)串顺序存储非紧凑格式的缺点是___。

我的答案：

(1) 空间利用率低

(填空题)字符串按存储方式可以分为：顺序存储,链接存储和___。

我的答案：

(1) 堆分配存储

(判断题)在链串中为了提高存储密度,应该增大结点的大小。

A. 对
B. 错

我的答案: 对

(判断题)串是n个字母的有限序列(n≥0)。

A. 对
B. 错

我的答案: 错

(判断题)广义表不能递归。

A. 对
B. 错

我的答案: 错

第六章（树）

(单选题) 在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,那么度为0的结点数有( )个。

A. 4
B. 5
C. 6
D. 7

我的答案: A 正确答案: C

（第一种解法：没看懂，叶子的度数为0；那么设叶子数为x，则此树的总分叉数为1* 4+ 2 * 2+ 3* 1+ 4* 1=15；此树的节点个数为16（此处涉及到一个公式;节点数=分叉数+1，由图形便可以观察出来）。又根据题目可以知道顶点数目还可以列出一个式子：4+2+1+1+x便可以得到等式：4+2+1+1+x=16；x=8为叶子数。）

（第二种解法：设该树总共有n个节点,则n=n0+n1+n2+n3.

该树中除了根节点没有前驱以外,每个节点有且只有一个前驱,因此有n个节点的树的总边数为n-1条.根据度的定义,总边数与度之间的关系为：n-1=0n0+1n1+2n2+3n3.

联立两个方程求解,可以得到n0=6）

(单选题) 某二又树的后序遍历序列为DABEC,中序遍历序列为DEBAC,则先序遍历序列为()。(过程写在课本上)

A. ACBED
B. DECAB
C. DEABC
D**. CEDBA**

正确答案: D

(单选题) 已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为( )。

A. 1
B. 2
C. 3
D. 4

***的答案: B 正确答案: B

（完全二叉树最大结点数是2的k次方 - 1，k表示深度，所以，总数9的结点数，深度应该是4，前3层共结点数2的3次方 -1 = 7， 9 - 7 等于2，所以最后一层结点数是2）

(单选题) 假设在一棵二叉树中,双分支结点数为15,单分支结点数为30个,则叶子结点数为( )个。

A. 15
B. 16
C. 17
D. 47

***的答案: B 正确答案: B

在数据结构中一般常用的公式为：二叉树：度为0的节点数=度为2的节点数+1（n0=15+1=16）此公式可由上述计算思想推导）

(单选题) 具有35个结点的完全二叉树的深度为( )。

A. 5
B. 6
C. 7
D. 8

***的答案: B 正确答案: B

节点个树n和树深k的关系

所以节点个树n和树深k的关系为：2^k-1=n
所以树深：k=log_2(n+1)或者⌊log₂n⌋+1 ?

(单选题) 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组a[1]~a[n]中,结点a[i]若有左孩子,其左孩子的编号为结点( )。

A. a[2i+1]
B. a[2i-1]
C. a[i/2]
D. a[2i]

***的答案: D 正确答案: D

因为在完全二叉树中，左孩子的位置是当前结点的位置乘以2。

(单选题) 二叉树的先序遍历序列为ABC的不同二叉树有( )种形态。

A. 3
B. 4
C. 5
D. 6

***的答案: C 正确答案: C

(填空题) 一棵深度为k的满二叉树的结点总数为（）,一棵深度为k的完全二叉树的结点总数的最小值为（）,最大值为（）。

***的答案：

(1)2^k-1

(2) 2^(k-1)

(3) 2^k-1
正确答案：

(1) 2^k-1

(2) 2^(k-1)

(3) 2^k-1

(填空题) 先序序列和中序序列相同的二叉树为___。

***的答案：

(1) 没有左孩子
正确答案：

(1) 单右枝二叉树或孤立结点

(填空题) 由三个结点构成的二叉树,共有___种不同的结构。

***的答案：

(1) 5
正确答案：

(1) 5

(填空题) 假定一棵树的广义表表示法为A(B(E),C(F(H,I,J),G),D),则该树的度为（）,树的深度为（）,终端结点的个数为（）,单分支结点的个数为（）,双分支的结点个数为（）,三分支的结点个数为（）,C结点的双亲结点为（）,其孩子结点为（）和（）结点。

***的答案：

(1) 3

(2) 4

(3) 6

(4) 1

(5) 1

(6) 2

(7) A

(8) F

(9) G
正确答案：

(1) 3

(2) 4

(3) 6

(4) 1

(5) 1

(6) 2

(7) A

(8) F

(9) G

(填空题) 哈夫曼树是指___的二叉树。

***的答案：

(1) 最优
正确答案：

(1) 带权路径长度最小

(填空题) 设一棵二叉树共有50个叶子结点(终端结点),则有___个度为2的结点。

***的答案：

(1) 49
正确答案：

(1) 49

在数据结构中一般常用的公式为：二叉树：度为2的节点数=度为0的节点数-1（n0=50-1=49）此公式可由上述计算思想推导）

(填空题) 对于一个具有n个结点的二叉树,当它为一棵（）二叉树时,具有最小高度,即为（）,当它为一棵单支树时具有（）高度,即为（）。

***的答案：

(1) 完全

(2) log2n+1

(3) n

(4) 线性表
正确答案：

(1) 完全

(2) ⌊log₂n⌋+1

(3) 最大

(4) 线性表

(填空题) 对于二叉树来说,第i层上最多有___个结点。

***的答案：

(1) 2
正确答案：

(1) 2^(i-1)

(填空题) 由带权为3,6,2,5的4个叶子结点构成的一棵哈夫曼树,则带权路径长度为___。

***的答案：

(1) 31
正确答案：

(1) 31

构建哈夫曼树：

1、给其排序，2，3，5，6

2、找到其中最小的两数，开始画树，2，3

3、计算两数之和，并将该和加入到待找最小两数的数组里，跟着一起被选

如果选中的是两个原数组的数，则在旁边重开一个全新的分支

如果权值与一个原数组的数相同，则选择最小的这两个数，但是计算带权路径长度时不能带上它

4、算带权路径长度 2* 3（深度）+3* 3+6* 1=31

(填空题) 设F是森林,B是由F转换得到的二叉树,F中有n个非终端结点,B中右指针域为空的结点有___。

***的答案：

(1) n+1
正确答案：

(1) n+1

在将森林F转换为二叉树B时，每个非终端节点都会转换为一个二叉树节点。由于B是二叉树，每个节点最多只有两个指针域，即左指针和右指针。在转换过程中，每个非终端节点都会在B中生成一个包含自身的二叉树节点，而这个节点的右指针域为空。

(判断题) 由树转换成二叉树,其根结点的右子树一定为空。

A. 对
B. 错

***的答案: 对 正确答案: 对

(判断题) 树结构中的每个结点最多只有一个直接前驱。

A. 对
B. 错

***的答案: 对 正确答案: 对

第七章（图）

(单选题) 下列说法不正确的是( )。

A. 图的遍历是从给定的源点出发每一个顶点仅被访问一次
B. 遍历的基本算法有两种：深度优先遍历和广度优先遍历
C. 图的深度优先遍历不适用于有向图
D. 图的深度优先遍历是一个递归过程

我的答案:C正确答案: C

(单选题) 一个n个顶点的连通无向图,其边的个数至少为( )。

A. n-1
B. n
C. n+1
D. nlog₂n

我的答案: A正确答案: A

(单选题) 要连通具有n个顶点的有向图,至少需要( )条边。

A. n-1
B. n
C. n+1
D. 2n

我的答案: B正确答案: B

(单选题) 无向图G=(V,E),其中：v={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)｝,对该图进行深度优先遍历,得到的顶点序列正确的是( )。

A. a,b,e,c,d,f
B. a,c,f,e,b,d
C. a,e,b,c,f,d
D. a,e,d,f,c,b

我的答案: D正确答案: D

DFS的原理

DFS算法的特点是从根顶点出发，

\1. 访问所到达的顶点v。

\2. 前往v的未被访问的邻接点。

若v的所有邻接点均被访问过，则回溯到访问历史中v的上一个顶点v’，对其进行第2步，即访问v’除v之外的其他邻接点；这种回溯可以一直到根顶点；若回溯到根顶点后仍有节点未被访问，且不与根顶点邻接，则更换根节点。

解析：

A. a, b, e, c, d, f

a->b, 没问题；到b后，b的邻接点中只剩下e未被访问，b->e没问题

e->c，不行，e此时仍有未被访问的邻接点d, 且e没有跟c连通，答案错误

B. a, c, f, e, b, d

a->c->f, 没问题；f->e，不行，f此时仍有未被访问的邻接点d，且f没有跟e连通，答案错误

C. a, e, b, c, f, d

a->e->b，没问题；到b后，b的邻接点均被访问，应回溯到e，然后访问e其他未被访问的邻接点（只剩d），且b没有跟c连通，答案错误

D. a, e, d, f, c, b

a->e->d->f->c，没问题；到c后，其两个邻接点a与f均已被访问，按c->f->d->e->a回溯时候发现，e顶点仍有未被访问的顶点b，于是a->e->d->f->c->b

(单选题) 用邻接表表示图进行广度优先遍历时,通常采用( )来实现算法。

A. 栈
B. 队列
C. 树
D. 图

我的答案: B正确答案: B

(单选题) 用邻接表表示图进行深度优先遍历时,通常采用( )来实现算法。

A. 栈
B. 队列
C. 树
D. 图

我的答案: A正确答案: A

(单选题) 无向图顶点V的度是关联于该顶点( )的数目。

A. 顶点
B. 边
C. 序号
D. 下标

我的的答案:B正确答案: B

每个顶点所拥有的边的个数叫作度

(单选题) 图中有关路径的定义是( )。

A. 由顶点和相邻顶点序偶构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是

我的答案: A正确答案: A

(单选题) n个结点的完全有向图含有边的数目( )。

A. n*n
B. n(n+1)
C. n/2
D. n*(n-1)

我的答案: D正确答案: D

(单选题) 设无向图的顶点个数为n,则该图最多有( )条边。

A. n-1
B. n(n-1)/2
C. n+1
D. 0
E. n²

我的答案: B正确答案: B

(单选题) 一个无向图有5个顶点、8条边,则其生成树将要去掉( )条边。

边至少为5-1条

A. 3
B. 4
C. 5
D. 6

我的答案: B正确答案: B

(单选题) 任何一个无向连通图的最小生成树( )。

A. 只有一棵
B. 一棵或多棵
C. 一定有多棵
D. 可能不存在

正确答案: A

(多选题) 在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等千所有顶点出度之和的( )倍。

A. 1/2
B. 2
C. 1
D. 4

我的答案: BC正确答案: BC

(多选题) 一个有n个结点的图,最少有( )个连通分量,最多有( )个连通分量。

A. 0
B. 1
C. n-1
D. n

正确答案: BD

(填空题) G是一个非连通无向图,共有28条边,则该图至少有___个顶点。

用到无向图公式n(n-1)/2，n为顶点数，而最后因为是非连通图所以还要n+1为9

我的答案：

(1) 9
正确答案：

(1) 9

(填空题) 具有10个顶点的无向图,边的总数最多为___。

我的答案：

(1) 45
正确答案：

(1) 45

(填空题) 一个连通图的___是一个极小连通子图。

我的答案：

(1) 生成树
正确答案：

(1) 生成树

(填空题) 如果含n个顶点的图形形成一个环,则它有___棵生成树。

我的答案：

(1) n
正确答案：

(1) n

(填空题) 有向图的强连通分量是指___。

我的答案：

(1) 有向图的极大强连通子图
正确答案：

(1) 有向图的极大强连通子图

(填空题) 在有n个顶点的有向图中,每个顶点的度最大可达___。

一个出度一个入度，所以*2

我的答案：

(1) 2(n-1)
正确答案：

(1) 2(n-1)

(填空题) N个顶点的连通图的生成树含有___条边。

我的答案：

(1) N-1
正确答案：

(1) N-1

(填空题) 判断一个无向图是一棵树的条件是___。

我的答案：

(1) 有n个顶点,n-1条边的无向连通图
正确答案：

(1) 有n个顶点,n-1条边的无向连通图

(填空题) 若用n表示图中顶点数目,则有___条边的无向图成为完全图。

注意这里是题目是完全图，一般如果是有向或者连通图就n，无向则为n-1

我的答案：

(1) n(n-1)/2
正确答案：

(1) n(n-1)/2

(判断题) 有向图不能进行广度优先遍历。

A. 对
B. 错

我的答案:错正确答案: 错

(判断题) 带权图最小生成树是唯一的。

A. 对
B. 错

我的答案: 错正确答案: 错

(判断题) 若以某个顶点开始,对有n个顶点的有向图G进行深度优先遍历,所得的遍历序列唯一,则可以断定其弧数为n-1。

A. 对
B. 错

我的答案:错正确答案: 错

第八章（查找）

(单选题)顺序查找法适合于存储结构为( )的线性表。

A. 散列存储
B. 顺序存储或是链式存储
C. 压缩存储
D. 索引存储

我的答案: B:顺序存储或是链式存储;

(单选题)用折半查找表的元素的速度比用顺序法( )。

A. 必然快
B. 必然慢
C. 相等
D. 不能确定

我的答案: D:不能确定;

(单选题)当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( )。

A. 必定快
B. 不一定
C. 在大部分情况下要快
D. 取决于表递增还是递减

我的答案: C:在大部分情况下要快;

(单选题)下面关于哈希(Hash,杂凑)查找的说法正确的是( )

A. 哈希函数构造的越复杂越好,因为这样随机性好,冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数,要视情况而定
D. 若需在哈希表中删去一个元素,不管用何种方法解决冲突都只要简单的将该元素删去即可

我的答案: C:不存在特别好与坏的哈希函数,要视情况而定;

(单选题)如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用( )查找方法。

A. 分块
B. 顺序
C. 折半
D. 散列

我的答案: A

(填空题)在分块查找方法中,首先查找(),然后再查找相应的___。

我的答案：

(1) 索引

(2) 块

(填空题)在分块查找方法中,表中每块内的元素可以(),块与块之间必须按___存放。

我的答案：

(1) 任意存放

(2) 关键字有序

(填空题)顺序查找、折半查找、分块查找都属于___查找。

我的答案：

(1) 静态

(填空题)在线性表的哈希存储中,装填因子ɑ又称为装填系数,若用m表示哈希表的长度,n表示线性表中的元素的个数,则ɑ等于___。

我的答案：

(1) n/m

(判断题)在二叉排序树中,根结点的值都小于孩子结点的值。

A. 对
B. 错

我的答案: 错

(判断题)直接插入排序时,关键字的比较次数与记录的初始排列无关。

A. 对
B. 错

我的答案: 对

(判断题)排序要求数据一定要按顺序方式存储。

A. 对
B. 错

我的答案: 错

(判断题)对千两棵具有相同关键字但形状不同的二叉排序树,按中序遍历它们得到的序列的顺序是一样的。

A. 对
B. 错

我的答案: 对

(单选题)二叉排序树的查找效率与二叉树的 (1) 有关，在 (2) 时其查找效率最低。

(1) (单选题) 1

A. 高度
B. 结点的多少
C. 树型
D. 结点的位置

我的答案: C

(2) (单选题) 2

A. 结点太多
B. 完全二叉树
C. 呈单枝树
D. 结点太复杂。

我的答案: C

数据结构

题目

第三章

学习通

第一章(基础概念)

(填空题) 一个算法具有5个特性： , , ，有零个或多个输入、有一个或多个输出。

(判断题) 算法可以用不同的语言描述，如果用C 语言或C++语言等高级语言来描述，则算法实际上就是程序了。

数据结构的操作的定义与具体实现有关。

(判断题) 数据项是数据不可分割的最小单位。

第二章（线性表）

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

线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（）。

(填空题) 在一个长度为n的顺序表中第i个位置（1≤i≤n+1）插入一个元素时，需向后移动（）个元素。

第三章

第四章（栈和队列）

(单选题) 循环队列占用的空间( )。

(填空题) 顺序队列初始化后, front=rear=___。

(判断题) 栈和队列都是顺序存储的线性结构。

第五章（串和广义表）

(单选题)设有一个字符串S=”abcdefgh”,问该串的最大子串个数为( )。

串的最大子串个数计算

(填空题)串链接存储的优点是（）,缺点是（）。

(填空题)串顺序存储紧凑格式的缺点是对串的字符处理___。

(填空题)空格串的长度等于___。

串的函数

(填空题)串顺序存储非紧凑格式的缺点是___。

(判断题)串是n个字母的有限序列(n≥0)。

(判断题)广义表不能递归。

第六章（树）

(单选题) 在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点数为2个,那么度为0的结点数有( )个。

(单选题) 某二又树的后序遍历序列为DABEC,中序遍历序列为DEBAC,则先序遍历序列为()。(过程写在课本上)

(单选题) 已知一棵完全二叉树的结点总数为9个,则最后一层的结点数为( )。

节点个树n和树深k的关系

(单选题) 用顺序存储的方法将完全二叉树中所有结点逐层存放在数组a[1]~a[n]中,结点a[i]若有左孩子,其左孩子的编号为结点( )。

(单选题) 二叉树的先序遍历序列为ABC的不同二叉树有( )种形态。

(填空题) 一棵深度为k的满二叉树的结点总数为（）,一棵深度为k的完全二叉树的结点总数的最小值为（）,最大值为（）。

(填空题) 先序序列和中序序列相同的二叉树为___。

(填空题) 哈夫曼树是指___的二叉树。

(填空题) 设一棵二叉树共有50个叶子结点(终端结点),则有___个度为2的结点。

(填空题) 对于一个具有n个结点的二叉树,当它为一棵（）二叉树时,具有最小高度,即为（）,当它为一棵单支树时具有（）高度,即为（）。

(填空题) 对于二叉树来说,第i层上最多有___个结点。

(填空题) 由带权为3,6,2,5的4个叶子结点构成的一棵哈夫曼树,则带权路径长度为___。

(填空题) 设F是森林,B是由F转换得到的二叉树,F中有n个非终端结点,B中右指针域为空的结点有___。

第七章（图）

(单选题) 下列说法不正确的是( )。

DFS的原理

(单选题) 任何一个无向连通图的最小生成树( )。

(多选题) 在一个无向图中,所有顶点的度数之和等于所有边数( )倍,在一个有向图中,所有顶点的入度之和等千所有顶点出度之和的( )倍。

(多选题) 一个有n个结点的图,最少有( )个连通分量,最多有( )个连通分量。

(填空题) G是一个非连通无向图,共有28条边,则该图至少有___个顶点。

(填空题) 一个连通图的___是一个极小连通子图。

(填空题) 如果含n个顶点的图形形成一个环,则它有___棵生成树。

(填空题) 有向图的强连通分量是指___。

(填空题) 在有n个顶点的有向图中,每个顶点的度最大可达___。

(填空题) N个顶点的连通图的生成树含有___条边。

(填空题) 判断一个无向图是一棵树的条件是___。

(填空题) 若用n表示图中顶点数目,则有___条边的无向图成为完全图。

(判断题) 有向图不能进行广度优先遍历。

(判断题) 带权图最小生成树是唯一的。

(判断题) 若以某个顶点开始,对有n个顶点的有向图G进行深度优先遍历,所得的遍历序列唯一,则可以断定其弧数为n-1。

第八章（查找）

(填空题)在分块查找方法中,首先查找(),然后再查找相应的___。

(填空题)在分块查找方法中,表中每块内的元素可以(),块与块之间必须按___存放。

(填空题)顺序查找、折半查找、分块查找都属于___查找。

(填空题)在线性表的哈希存储中,装填因子ɑ又称为装填系数,若用m表示哈希表的长度,n表示线性表中的元素的个数,则ɑ等于___。

(判断题)在二叉排序树中,根结点的值都小于孩子结点的值。

(判断题)直接插入排序时,关键字的比较次数与记录的初始排列无关。

(判断题)对千两棵具有相同关键字但形状不同的二叉排序树,按中序遍历它们得到的序列的顺序是一样的。

(单选题)二叉排序树的查找效率与二叉树的 (1) 有关，在 (2) 时其查找效率最低。

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